https://github.com/topepo/rstudio-conf-2018

1 Getting started

1.1 Course Overview

The session will step through the process of building, visualizing, testing and comparing models that are focused on prediction. The goal of the course is to provide a through workflow in R that can be used with many different regression or classification techniques. Case studies are illustrated functionality.

The goal is to be able to easily build predictive/machine learning models in R using a variety of packages and model types. - “Moldes that are focused on prediction”: what does that mean? - “Machine learning”: so this is deep learning with massive data sets, right?

The course is broken up into sections for regression (predicting numeric outcome) and classification (predicting a category).

1.2 Why R for modeling?

  1. R has cutting edge models. Machine learning developers in some domains use R as their primary computing environment and their work often results in R packages.
  2. It is easy to port or link to other applications. R doesn’t try to be everything to everyone. If you prefer models implemented in C, C++, tensorflow, keras, python, stan, or Weka, you can access these applications without leaving R.
  3. R and R packages are built by people who do data analysis.
  4. The S language is very mature.
  5. The machine learning environment in R is extremely rich.

1.3 Downsides to modeling in R

  1. R is a data analysis language and is not C or Java. If a high performance deployment is required, R can be treated like a prototyping language.
  2. R is s mostly memory-bound. There are plenty of exceptions to this though.
  3. The main issue is one of consistency of interface.

For example: - here are two methods for specifying what terms are in a model1. Not all models have both. - 99% of model functions automatically generate dummy variables. - Sparse matrices can be used (unless the can’t).

1.4 Syntax for computing predicted class probabilities

Function Package Code
lda MASS predict(obj)
glm stats predict(obj, type = “response”)
gbm gbm predict(obj, type = “response”, n.trees)
mda mda predict(obj, type = “posterior”)
rpart rpart predict(obj, type = “prob”)
Weka RWeka predict(obj, type = “probability”)
logitboost LogitBoost predict(obj, type = “raw”, nIter)

1.5 Different philosophies used here

There are two main philosophies to data analysis code that will be discussed in this workshop:

The main traditional approach uses high-level syntax and is perhaps the most untidy code that you will encounter.

caret is the primary package for untidy predictive modeling: 1. More traditional R coding style. 2. High-level “I do that for you” syntax. 3. More comperehensive (for now) and less modlular. 4. Contains many optimizations and is easily parallelized.

The tidy modeling approach espouses the tenets of the tidyverse 1. Reuses existing data structures 2. Compose simple functions with the pipe 3. Embrase functional programming 4. Design for humans

This approach is exemplified by packages such as: modelr, broom, recipes, rsample, yardstick and tidyposterior.

1.6 Example data set - house prices

For regression problems, we will use the Ames IA housing data. There are 2,930 properties in the data.

The sale price was recorded along 81 predictors, including - Location (e.g. neighborhood) and lot information. - House components (garage, fireplace, pool, porch, etc.). - General assessments such as overall quality and condition. - Number of bedrooms, baths, and so on.

More details can be found in De Cock (2011, Journal of Statistics Education).

he raw data are at http://bit.ly/2whgsQM but we will use a processed version found in the AmesHousing package.

library(AmesHousing)
AmesHousing::ames_raw
library(AmesHousing)
ames_geo 
Assuming "Longitude" and "Latitude" are longitude and latitude, respectively

1.7 Example data set - Fuel economy

The data that are used here are an extended version of the ubiquitous mtcars data set. fueleconomy.gov was used to obtain fuel efficiency data on cars from 2015-18.

Over this time range, duplicate ratings were eliminated; these occur when the same car is sold for several years in a row. As a result, there are 3294 cars that are listed in the data. The predictors include the automaker and addition information about the cars (e.g. intake valves per cycle, aspiration method, etc).

In our analysis, the data from 2015-2017 are used for training to see if we can predict the 609 cars that were new in 2018.

These data are supplied in the GitHub repo.

1.8 Example data set - Predicting profession

OkCupid is an online data site that serves international users. Kim and Escobedo-Land (2015, Journal of Statistics Education) describe a data set where over 50,000 profiles from the San Fransisco area were made available by the company.

The data contains several types of fields:

  • a number of open text essays related to interests and personal descriptions
  • single choice type fields, such as profession, diet, gender, body type, etc.
  • multiple choice data, including languages spoken, etc.
  • no usernames or pictures were included.

We will try to predict whether someone has a profession in the STEM fields (science, technology, engineering, and math) using a random sample of the overall dataset.

1.9 Tidyverse syntax

Many tidyverse functions have syntax unlike base R code. For example:

  • vectors of variable names are eschewed in favor of functional programming. For example:
contains("Sepal")

# instead of
c("Sepal.Width", "Sepal.Length")
  • The pipe operator is preferred. For example:
merged <- inner_join(a, b)
# is equal to
merged <- a %>%
  inner_join(b)
  • Functions are more modular than their traditional analogs (dplyr’s filter and select VS base::subset).

1.10 Some example data manipulation code

library(tidyverse)

ames <- read_delim("http://bit.ly/2whgsQM", delim = "\t") %>%
  rename_at(vars(contains(' ')), funs(gsub(' ', '_', .))) %>%
  rename(Sale_Price = SalePrice) %>%
  filter(!is.na(Electrical)) %>%
  select(-Order, -PID, -Garage_Yr_Blt)
library()
ames <- ames_raw %>% 
  rename_at(vars(contains(' ')), funs(gsub(' ', '_', .))) %>%
  rename(Sale_Price=SalePrice) %>% 
  filter(!is.na(Electrical)) %>% 
  select(-Order,-PID, -Garage_Yr_Blt)
  
  
ames %>% 
  group_by(Alley) %>% 
  summarize(mean_price=mean(Sale_Price/1000),
            n=sum(!is.na(Sale_Price)))

1.11 Example ggplot2 code

library(ggplot2)
ggplot(ames,
       aes(x=Garage_Type,
           y=Sale_Price))+
  geom_violin()+
  coord_trans(y="log10")+
  xlab("Garage Type")+
  ylab("Sale Price")

1.12 Examples of purrr::map*

library(purrr)
# Summarize via purrr::map
by_alley <- split(ames, ames$Alley)
is_list(by_alley)
[1] TRUE
# glimpse(by_alley)
map(by_alley, nrow)
$`Grvl`
[1] 120

$Pave
[1] 78
map_int(by_alley, nrow)
Grvl Pave 
 120   78 
# work on no-list vectors too
ames %>% 
  mutate(Sale_Price=Sale_Price %>% 
           map_dbl(function(x)x/1000)) %>% 
  select(Sale_Price, Yr_Sold) %>% 
  head()

1.13 Quick data investigation

To get warmed up, let’s load the Ames data and do some basic investigations into the variables, such as exploratory visualizations or summary statistics. The idea is to get a feel for the data.

library(AmesHousing)
ames <- make_ames()

1.14 Where we go from here

Part 2 Basic Principles - Data Splitting, Models in R, Resampling, Tuning(rsample)

Part 3 Feature engineering preprocessing - Data treatment (recipes)

Part 4 Regression Modeling - Measuring Performance, penalized regression, multivariate adaptive regression splines (MARS), ensembles (yardstick, recipes, caret, earth, glmnet, tidyposterior, doParallel)

Part 5 Classification Modeling - Measuring Performance, trees, ensembles, naive Bayes (yardstick, recipes, caret, rpart, klaR, tidyposterior)

1.15 Resources

http://www.tidyverse.org/ R for Data Science Jenny’s purrr tutorial or Happy R Users Purrr Programming with dplyr vignette Selva Prabhakaran’s ggplot2 tutorial caret package documentation CRAN Machine Learning Task View

About these slides…. they were created with Yihui’s xaringan and the stylings are a slightly modified version of Patrick Schratz’s Metropolis theme.

2 Part2 Basic principles

2.1 Introduction

In this section, we will introduce concepts that are useful for any type of machine learning model: - modeling versus the model - data splitting - resampling - tuning parameters and overfitting - model tuning

Many of these topics will be put into action in later sections.

2.1.1 The modeling process

Common steps during model building are:

  • estimating model parameters (i.e., training models)
  • determining the values of tuning parameters that cannot be directly calculated from the data
  • model selection (within a model type) and model comparison (between types)
  • calculating the performance of the final model that will generalize to new data

Many books and course portray predictive modeling as a short sprint. A better analogy would be a marathon or campaign (depending on how hard the problem is).

2.1.2 What the modeing process usually look like

knitr::include_graphics("C:/Users/kojikm.mizumura/Desktop/Data Science/UseR 2018/Applied ML/intro-process-1.png")

2.2 Data usage

2.2.1 Data Splitting and spending

How do we “spend” the data to find an optimal model? We typically split data into training an test data sets:

  • Training set: these data are used to estimate model parameters and pick the values of the complexity parameter(s) for the model.
  • Test set: these data can be used to get an independent assessment of model efficacy. They should not be used during model training.

The more data we spend, the better estimates we’ll get (provided the data is accurate).

Given a fixed amount of data: - too much spent in training won’t allow us to get a good assessment of predictive peformance. We may find a model that fits the training data very well, but is not generalizable (overfitting) - too much spent in testing won’t allow us to get a good assessment of model parameters

Statisticall,y the est course of action would be use all the data for model building and use statistical methods to get estimates of error.

From a non-statistical perspective, many consmers of complex models emphasize the need for untouched set of sampled to evaluate performance.

2.2.2 Large data set

When a large amount of data are available, it might seem like a good idea to put a large amount into the training set. Personally, I think that this causes more trouble than it is worth due to diminishing returns on performance and the added cost and compexity of the required infrastructure.

Alternatively, it is probably a better idea to reserve good percentages of the data for specific parts of the modeling process. For example:

  • Save a large chunk of data to perform feature selection prior to model building
  • Retain data to calibrarate class probabilities or determine a cutoff via an ROC curve.

Also there may be little need for iterative resampling of the data. A single holdout (aka validation set) may be sufficient in some cases if the data are large enough and the data sampling mechanism is solid.

2.2.3 Mechanis of data splitting

There are a few different ways to do the split: simple random sampling, stratified sampling based on the outcome, by date, or methods that focus on the distribution of the predictors.

For stratification: - classification: this would mean sampling within the classes as to preserve the distribution of the outcome in the training and test sets - regression: determine the quartiles of the data set and samples within those artificial groups

2.2.4 Ames Housing data

ames <- make_ames()
dim(ames)
[1] 2930   81
library(rsample)
# make suret you get the same random numbers
set.seed(4595)
data_split <-initial_split(ames,strata="Sale_Price") 
ames_train <- training(data_split)
ames_test <- testing(data_split)
nrow(ames_train)/nrow(ames)
[1] 0.7505119

2.2.5 Outcome distribution

library(ggplot2)
# Do the distribution line-up?
ggplot(ames_train,aes(x=Sale_Price))+
   geom_line(stat = "density", 
            trim = TRUE) + 
  geom_line(data = ames_test, 
            stat = "density", 
            trim = TRUE, col = "red")

2.3 Creating models in R

2.3.1 Specifying models in R using formulas

To fit a model to the housing data, the model terms must be specified. Historically, there are two main interfaces for doing this.

The fomula interface using R fomula rules to specify a symbolic representation of the terms and variables. For example:

foo(Sale_Price ~ Neightborhood + Year_Sold + Neighborhood:Year_Sold, data=ames_train)

OR

foo(Sale_Price~., data=ames_train)

OR

foo(log10(Sale_Price)~ns(Longitude, df=3)+ns(Latitude,df=3),data=ames_train)

This is very convenient but it has some disadvantages.

2.3.2 Downsides to formulas

  • You can’t nest in-line functions such as foo(y ~ pca(scale(x1), scale(x2), scale(x3)), data =dat).
  • All the model matrix calculations happen at once and can’t be recycled when used in a model function.
  • For very wide data sets, the formula method can be extremely inefficient.
  • There are limited roles that variables can take which has led to several re-impementations of formulas.
  • Specifyng multivarite outcomes
  • Not all model functions have a formula method.

2.3.3 Specifying model without formulas

Some modeling function have the non-formula interface. This usually has arguments for the predictors and the outcome(s):

# Usually, the variable must all be numeric

pre_vars <- c("Year_Sold","Longitude","Latitude")
foo(x=ames_train[,pre_vars],
    y=ames_train$Sale_Price)

This is inconvenient if you have transformations, factor variables, interactions or any other operations apply prior to modeling.

Overall, it is difficult to predict if a package has one or both of these interfaces. For example, lm only has formulas.

There is a third interface using recipes that will be discussed later that solve some of these issues.

2.3.4 A linear regression model

Let’s start by fitting an ordinary linear regression model to the training set. You can choose the model terms for your model but I will use a very simple model:

head(ames_train)
simple_lm <- lm(log10(Sale_Price)~Longitude+Latitude, data=ames_train)

Before looking at coefficients, we should do some model checking to see if there is anything obviously wrong with the model.

To get the statistics on the individual points, we willl use the awesome broom package:

library(broom)
library(magrittr)
simple_lm_values <- augment(simple_lm)
simple_lm_values %>% names()
 [1] "log10.Sale_Price." "Longitude"         "Latitude"          ".fitted"          
 [5] ".se.fit"           ".resid"            ".hat"              ".sigma"           
 [9] ".cooksd"           ".std.resid"       

2.3.5 Hands-on: some basic diagnostics

From these results, let’s do some visualizations:

  • Plot the observed versus fitted values
  • Plot the residuals
  • Plot the predicted versus resdiduals

Are there any downsides to this approach?

2.4 Model evaluation

2.4.1 Overall model statistics

If you use the summary method on the lm object, the buttom shows some statistics.

summary(simple_lm)

Call:
lm(formula = log10(Sale_Price) ~ Longitude + Latitude, data = ames_train)

Residuals:
     Min       1Q   Median       3Q      Max 
-1.01769 -0.09771 -0.01536  0.10003  0.57637 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) -316.1528    15.0273  -21.04   <2e-16 ***
Longitude     -2.0792     0.1346  -15.45   <2e-16 ***
Latitude       3.0135     0.1880   16.03   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1614 on 2196 degrees of freedom
Multiple R-squared:  0.1808,    Adjusted R-squared:  0.1801 
F-statistic: 242.3 on 2 and 2196 DF,  p-value: < 2.2e-16

These statistics are the result of predicting the same data that was used to derive the coefficients. This is problematic because it can lead to optimistic results, especially for models that are extremely flexibile.

The test set is used for assessing performance. Should we predict the test set and use those results to estimate these statistics.

NOPE!

2.4.2 Assessing models

Save the test set until the very end when you have one or two models that are your favorite. We’ll need to use the training set but…

For some models, it is possible to get very small residuals by predicting the training set. That’s an issue since we will need to make comparisons between models, create diagnostic plots, etc.

If only we had a method for getting honest performance estimates from the training set..

2.4.3 Resampling methods

There are additional data splitting schemes that are applied to training set. They attempt to stimulate slightly different versions of the traing set. These versions of the original are split into two model subsets.

  • The analysis set is used to fit the model (analogous to the training set)
  • Performance is determined using the assessment set.

This process is repated many times. There are different flavors or resampling but we will focus on two methods.

2.4.4 V-Fold Cross-validation

knitr::include_graphics("C:/Users/kojikm.mizumura/Desktop/Data Science/UseR 2018/Applied ML/resampling methods.PNG")

These are additonal data splitting that are applied to the training set. They attempt to simpuate slightly different versions of the training set. These versions of the oroginal are split into two model subsets. - The analysis set ised o fit the model (analogous to the training set) - Peformance is determined using the assessment set.

This process is repeated many times.

There are different flavors or resampling but we will focus on two methods.

2.4.5 V-Fold Cross Validation

Here, we randomly split the training data into V distinct blocks of roughly equal size. - We leave out the first block of analysis data and fit a model. - This model is used to predict the held-out block of assessment data. - We continue this process until we’ve predicted all V assessment blocks.

The final performance is based on the hold-out predictions by averaging the statistics from the V blocks. V is usually taken to be 5 or 10 and leave one out cross-validation has each sample as a block.

2.4.6 10-Fold Cross-Validation with n=50

knitr::include_graphics("C:/Users/kojikm.mizumura/Desktop/Data Science/UseR 2018/Applied ML/cv-plot-1.png")

2.4.7 Bootstrapping

A boostrap sample is the same size as the training set but each data point is selected with replacement.

This means that the analysis set will have more than one replicate of a training set instance.

The assessment set contains all samples that were never included in the bootstrap set. It is often called the out-of-bag sample and can vary in size.

On average, 63.1220559% of the training set is contained at least once in the bootstrap sample.

knitr::include_graphics("C:/Users/kojikm.mizumura/Desktop/Data Science/UseR 2018/Applied ML/boot-plot-1.png")

2.4.8 Comparing Resampling methods

If you think of resampling in the same manner as statistical estimators (e.g., maximum likelihood), this becomes a trade-off bias and variance:

  • variance is (mostly) driven by the number of resamples (e.g., 5-fold CV larger variance than 10-folds).
  • Bias is (mostly) related to how much data is held back. The bootstrap has large bias compared to 10-fold CV.

There are length blog posts about this subject here and here.

I tend to favor 5 repeats of 10-fold cross-validation unless the size of the assessment data is “large enough”.

For example, 10% of the Ames training set is 219 properties and this is probably good enough to estimate the \(RMSE\) and \(R^2\).

2.4.9 Cross-validating using rsample

library(AmesHousing)
library(rsample)
set.seed(2433)
cv_splits <- vfold_cv(ames_train, v=10, strata="Sale_Price")
cv_splits
#  10-fold cross-validation using stratification 

The split objects contain the information about the sample size.

cv_splits$splits[[1]]
<1977/222/2199>

We use the analysis and assessment functions to get the data.

analysis(cv_splits$splits[[1]]) %>% dim()
[1] 1977   81
assessment(cv_splits$splits[[1]]) %>% dim()
[1] 222  81

2.4.10 Resampling the linear model

We Will need to write a function to fit the model to each data set and another to compute performance.

library(yardstick)
package 㠼㸱eyardstick㠼㸱f was built under R version 3.5.1
Attaching package: 㠼㸱eyardstick㠼㸱f

The following objects are masked from 㠼㸱epackage:caret㠼㸱f:

    mnLogLoss, precision, recall

The following object is masked from 㠼㸱epackage:readr㠼㸱f:

    spec

For performance, the first argument should the rsplit objected contained in cv_splits$splits:

model_perf <- function(data_split, mod_obj) {
  vars <- rsample::form_pred(mod_obj$terms)
  assess_dat <- assessment(data_split) %>%
      select(!!!vars, Sale_Price) %>%
      mutate(
          pred = predict(
              mod_obj, 
              newdata = assessment(data_split)
          ),
          Sale_Price = log10(Sale_Price)
      )
  rmse <- assess_dat %>% 
      rmse(truth = Sale_Price, estimate = pred)
  rsq <- assess_dat %>% 
      rsq(truth = Sale_Price, estimate = pred)
  data.frame(rmse = rmse, rsq = rsq)
}

2.4.11 Resamling the linear model

The purrr package will be used to fit the model to each analysis set. There will be saved in a column called lm_mod:

library(purrr)
cv_splits <- cv_splits %>% 
  mutate(lm_mod=map(splits, lm_fit, formula=form))
cv_splits
#  10-fold cross-validation using stratification 

2.4.12 Resampling the linear model (cont.)

Now, let’s compute the two performance measures:

# map2 can be used to move over two objects of equal length
library(dplyr)
lm_res <- map2_df(cv_splits$splits, cv_splits$lm_mod, model_perf) %>% 
  dplyr::rename(rmse_simple=rmse, rsq_simple=rsq)
lm_res %>% head()
# Merge in results:
cv_splits <- cv_splits %>% bind_cols(lm_res)
# Rename the columns and compute the resampling estimates:
cv_splits %>% select(rmse_simple, rsq_simple) %>% colMeans
rmse_simple  rsq_simple 
  0.1612427   0.1845147 

2.4.13 What was the ruckus?

Previously, I mentioned that the performance metrics that were naively calculated from the training set could be optimistic. However, this approach estimates the RMSE to be 0.1614, and cross-validation produced an estimate of 0.1613. What was trhe big deal?

Linear regression is a high bias model. This means that it is fairly incapable at beign able to adpt the underlying model function (unless it is linear). For this reason, linear regression is unlikely to overfit to the training set and our two estimates are likely to be the same.

We’ll consider another model shortly that is low bias since it can, theoretically, easily adapt to a wide variety of true model functions.

However, as before, there is also variance to consider. Linear regression is very stable since it leverages all of the data points to estimate parameters. Other methods, such as tree-based models, are not and can drastically change if the training set data is slightly perturbed.

tl;dr: the earlier concern is real but linear regression is less likely to be affected.

2.4.14 Diagnostics Again

Now let’s look at diagnostics using the predictions from the assessment sets.

get_assessment <- function(splits, model)
  augment(model, newdata=assessment(splits)) %>% 
  mutate(.resid=log10(Sale_Price)-.fitted)
holdout_results <- map2_df(cv_splits$splits, cv_splits$lm_mod, get_assessment)
holdout_results %>% dim()
[1] 2199   84
ames_train %>% dim()
[1] 2199   81

2.4.15 Hands-on partial residual plots

A partial residual plot is used to diagnose what variables should have been in the model.We can plot the hold-out residuals versus different variables to understand if they should have been in the model - If the residuals have no pattern in the data, they are likely to be irrelevant. - If a pattern is seen, it suggests that the variable should have been in the model.

Take 10 min and use ggplot to investigate other predictors using the holdout_results data frame. geom_smooth might come in handy.

2.5 Tuning parameters and overfitting

2.5.1 K-Nearest Neighbors Model

Now let’s consider a more flexible model that is low bas: K-nearest neighbors.The model stores the training set(including the outcome). When a new sample is predicted, \(K\) training set points are found that are most similar to the new sample being predicted.

The predicted value for the new sample is some summary statistic of the neighbors, usually: - the mean for regression, or - the mode for classification

When \(K\) is small, the model might be too responsive to underlying data. When \(K\) is large, it begins to “oversmooth” the neighbors and performance suffers.

Ordinary, since we are computing a distance, we would want to center and scale the predictors. Our two predictors are already on the same scale so we can skip this step.

Consider the 2-nearest neighbor model. Would there be a difference in the estimated model performance between re-prediction and cross-validation?

caret has a knnreg function that can be used (the kknn package is another option). IT has a formula method and we’ll use this to illustrate the model:

library(caret)
knn_train_mod <- knnreg(log10(Sale_Price)~Longitude+Latitude,
                        data=ames_train,
                        k=2)
repredict <- data.frame(price=log10(ames_train$Sale_Price)) %>% 
  mutate(pred=predict(knn_train_mod, newdata=ames_train %>% select(Longitude,Latitude)
                      )
         )
repredict %>% rsq(truth = "price", estimate = "pred") # <- the ruckus is here
Error in rsq(., truth = "price", estimate = "pred") : 
  could not find function "rsq"

Thats pretty good, but are we tricking ourselves? One of those two neighbors is always itself. To resample, let’s create another function to fit this model and follow the same resampling process as before:

knn_fit <- function(data_split,...)
  knnreg(..., data=analysis(data_split))
cv_splits <- cv_splits %>% 
  mutate(knn_mod=map(splits, knn_fit, formula=form, k=2))
knn_res <- map2_df(cv_splits$splits, cv_splits$knn_mod, model_perf) %>% 
  rename(rmse_knn=rmse, rsq_knn=rsq)
# merge in results
cv_splits <- cv_splits %>% bind_cols(knn_res)
colMeans(knn_res)
 rmse_knn   rsq_knn 
0.1012993 0.6869034 

2.5.2 Making formal comparisons

The model appears to be a drastic improvement over simple linear regression, but we are definitely getting highly optimistic results by re-predicting the training set.

We can try to make a more formal assesment of the two current models. Both models used the same resamples, so we have 10 estimates of performance that are matched. Does the matching mean anything?

Most likely YES. It is very common to see that there is a resample effect. Similar to repeated measures designs, we can expect a relationship between models and resamples. For example, some resamples will have the worst performance over different models and so on.

In other words, there is usually a within-resample correlation. For the two models, the estimated correlation in RMSE values is 0.85.

2.5.3 The resample effect

2.5.4 Model comparison accounting for resampling

With only two models, a paired t-test can be used to estimate the difference in RMSe between the models:

t.test(cv_splits$rmse_simple, cv_splits$rmse_knn, paired=TRUE)

    Paired t-test

data:  cv_splits$rmse_simple and cv_splits$rmse_knn
t = 21.265, df = 9, p-value = 5.282e-09
alternative hypothesis: true difference in means is not equal to 0
95 percent confidence interval:
 0.05356677 0.06632000
sample estimates:
mean of the differences 
             0.05994338 

Hothorn et al (2012) is the original paper on comparing models using resampling.

We’ll do more extensive analyses with tidyposterior soon.

2.5.5 Overfitting

Overfitting occurs when a model inappropriately pick up on trends in the training set that do not generalize to new samples. When this occurs, assesment of the model based on the training set can show good performance that does not reproduce in future samples.

Some models have specific “knobs” to control over-fitting - neighborhood size in nearest neighbor models is an example - the number of splits in a tree model

often poor choices for these parameters can result in overfitting

For example, the next slide shows a data set with two predictors. We want to be able to produce a line (i.e., decision boundary) that differentiates two classes of data.

2.5.6 Two class example,

On the next slide, two classification boundaries are shown for a different model type not yet discussed. The differece in the two panes is solely due to different choices in tuning parameters. One overfits the training data.

We usually don’t have two-dimensional data so a quantitative method for under measureing overfitting is needed. Resampling fits that description. A simple method for tuning a model is used to grid search:

├── Create a set of candidate tuning parameter values └── For each resample │ ├── Split the data into analysis and assessment sets │ ├── [preprocess data] │ ├── For each tuning parameter value │ │ ├── Fit the model using the analysis set │ │ └── Compute the performance on the assessment set and save ├── For each tuning parameter value, average the performance over resamples ├── Determine the best tuning parameter value └── Create the final model with the optimal parameter(s) on the training set

Random search is a similar technique where the candidate set of parameter values are simulated at random across a wide range. Also, an example of nested resampling can be found here.

2.5.7 Grid search computations

The bad news is that all of the models (except the final model) are discared. However, as the good news, all of the models (except the final model) can be run in parallel. Let’s look at the Ames K-NN model and evaluate \(K=1,2,\dot,20\) using the same 10-fold cross-validation as before.

We’ll start coding this algorithm from the inside out.

These steps are: ├── Fit the model using the analysis set └── Compute the performance on the assessment set and save

split will be the one of elements of cv_splits$splits.

knn_rmse <- function(k, split) {
    mod <- knnreg(log10(Sale_Price) ~ Longitude + Latitude, 
                                data = analysis(split),  
                                k = k)
    # Extract the names of the predictors
    preds <- form_pred(mod$terms)
    data.frame(Sale_Price = log10(assessment(split)$Sale_Price)) %>%
        mutate(pred = predict(mod, assessment(split) %>% select(!!!preds))) %>%
        rmse(Sale_Price, pred)
}

2.5.8 Fit the model across values of K

│ ├── For each tuning parameter value │ │ └── Run knn_rmse

knn_grid <- function(split) {
    # Create grid
  tibble(k = 1:20) %>%
    # Execute grid for this resample
    mutate(
      rmse = map_dbl(k, knn_rmse, split = split),
      # Attach the resample indicators using `lables`
      id = labels(split)[[1]]
    )
}

The return values here is a tibble with columns for k, the RMSE, and the fold ID (e.g., Fold01).

2.5.9 Top-level iteration over resamples

└── For each resample │ └── Run knn_grid

Here, resamp is the resample object cv_splits

iter_over_resamples <- 
    function(resamp) 
        map_df(resamp$splits, knn_grid)

2.5.10 Running the code

library(rsample)
knn_tune_res <- iter_over_resamples(cv_splits)
knn_tune_res %>% head(15)

2.5.11 The performance profile

To summarize the results for each value of \(K\):

library(tidyverse)
rmse_by_k <- knn_tune_res %>% 
  group_by(k) %>% 
  summarize(rmse=mean(rmse))
ggplot(rmse_by_k, aes(x=k, y=rmse))+
  geom_point()+geom_line()

Although it is numerically optimal, we are not required to use a value of 4 neighbors for the final model.

2.5.12 Resampling variation

How stable is this? We can also plot the individual curves and their minimums.

LS0tDQp0aXRsZTogIkFwcGxpZWQgTWFjaGluZSBMZWFybmluZyBieSBSU3R1ZGlvMjAxNyINCmF1dGhvcjogIktvamkgTWl6dW11cmEiDQpkYXRlOiAnIE9jdG9iZXIgMjIsIDIwMTgnDQphbHdheXNfYWxsb3dfaHRtbDogeWVzDQpvdXRwdXQ6DQogIGh0bWxfbm90ZWJvb2s6DQogICAgY29kZV9mb2xkaW5nOiBoaWRlDQogICAgZmlnX2hlaWdodDogNC41DQogICAgZmlnX3dpZHRoOiA3DQogICAgaGlnaGxpZ2h0OiB0YW5nbw0KICAgIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgdGhlbWU6IGNvc21vDQogICAgdG9jOiB5ZXMNCiAgd29yZF9kb2N1bWVudDoNCiAgICB0b2M6IHllcw0KICBodG1sX2RvY3VtZW50Og0KICAgIGRmX3ByaW50OiBwYWdlZA0KICAgIHRvYzogeWVzDQotLS0NCg0KaHR0cHM6Ly9naXRodWIuY29tL3RvcGVwby9yc3R1ZGlvLWNvbmYtMjAxOCAgDQoNCmBgYHtyIGluY2x1ZGU9RkFMU0V9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkgI3RpZHlpbmcNCmxpYnJhcnkobWFncml0dHIpICN0aWR5aW5nDQpsaWJyYXJ5KHJzYW1wbGUpDQoNCmxpYnJhcnkoQW1lc0hvdXNpbmcpICNkYXRhDQogDQpsaWJyYXJ5KHJlY2lwZXMpICNwcmUtcHJvY2Vzc2luZw0KbGlicmFyeShjYXJldCkgIyBtb2RlbGluZw0KbGlicmFyeShBcHBsaWVkUHJlZGljdGl2ZU1vZGVsaW5nKSAjIG1vZGVsaW5nDQpsaWJyYXJ5KGJyb29tKSAjIG1vZGVsaW5nDQpgYGANCg0KIyBHZXR0aW5nIHN0YXJ0ZWQNCiMjIENvdXJzZSBPdmVydmlldw0KDQpUaGUgc2Vzc2lvbiB3aWxsIHN0ZXAgdGhyb3VnaCB0aGUgcHJvY2VzcyBvZiBidWlsZGluZywgdmlzdWFsaXppbmcsIHRlc3RpbmcgYW5kIGNvbXBhcmluZyBtb2RlbHMgdGhhdCBhcmUgZm9jdXNlZCBvbiBwcmVkaWN0aW9uLiBUaGUgZ29hbCBvZiB0aGUgY291cnNlIGlzIHRvIHByb3ZpZGUgYSB0aHJvdWdoIHdvcmtmbG93IGluIFIgdGhhdCBjYW4gYmUgdXNlZCB3aXRoIG1hbnkgZGlmZmVyZW50IHJlZ3Jlc3Npb24gb3IgY2xhc3NpZmljYXRpb24gdGVjaG5pcXVlcy4gQ2FzZSBzdHVkaWVzIGFyZSBpbGx1c3RyYXRlZCBmdW5jdGlvbmFsaXR5Lg0KDQpUaGUgZ29hbCBpcyB0byBiZSBhYmxlIHRvIGVhc2lseSBidWlsZCBwcmVkaWN0aXZlL21hY2hpbmUgbGVhcm5pbmcgbW9kZWxzIGluIFIgdXNpbmcgYSB2YXJpZXR5IG9mIHBhY2thZ2VzIGFuZCBtb2RlbCB0eXBlcy4gDQotICJNb2xkZXMgdGhhdCBhcmUgZm9jdXNlZCBvbiBwcmVkaWN0aW9uIjogd2hhdCBkb2VzIHRoYXQgbWVhbj8NCi0gIk1hY2hpbmUgbGVhcm5pbmciOiBzbyB0aGlzIGlzIGRlZXAgbGVhcm5pbmcgd2l0aCBtYXNzaXZlIGRhdGEgc2V0cywgcmlnaHQ/DQoNClRoZSBjb3Vyc2UgaXMgYnJva2VuIHVwIGludG8gc2VjdGlvbnMgZm9yIHJlZ3Jlc3Npb24gKHByZWRpY3RpbmcgbnVtZXJpYyBvdXRjb21lKSBhbmQgY2xhc3NpZmljYXRpb24gKHByZWRpY3RpbmcgYSBjYXRlZ29yeSkuDQoNCiMjIFdoeSBSIGZvciBtb2RlbGluZz8NCjEuIFIgaGFzICpjdXR0aW5nIGVkZ2UgbW9kZWxzKi4gTWFjaGluZSBsZWFybmluZyBkZXZlbG9wZXJzIGluIHNvbWUgZG9tYWlucyB1c2UgUiBhcyB0aGVpciBwcmltYXJ5IGNvbXB1dGluZyBlbnZpcm9ubWVudCBhbmQgdGhlaXIgd29yayBvZnRlbiByZXN1bHRzIGluIFIgcGFja2FnZXMuDQoyLiBJdCBpcyBlYXN5IHRvIHBvcnQgb3IgbGluayB0byBvdGhlciBhcHBsaWNhdGlvbnMuIFIgZG9lc24ndCB0cnkgdG8gYmUgZXZlcnl0aGluZyB0byBldmVyeW9uZS4gSWYgeW91IHByZWZlciBtb2RlbHMgaW1wbGVtZW50ZWQgaW4gYENgLCBgQysrYCwgYHRlbnNvcmZsb3dgLCBga2VyYXNgLCBgcHl0aG9uYCwgYHN0YW5gLCBvciBgV2VrYWAsIHlvdSBjYW4gYWNjZXNzIHRoZXNlIGFwcGxpY2F0aW9ucyB3aXRob3V0IGxlYXZpbmcgUi4NCjMuIFIgYW5kIFIgcGFja2FnZXMgYXJlIGJ1aWx0IGJ5IHBlb3BsZSB3aG8gKipkbyoqIGRhdGEgYW5hbHlzaXMuDQo0LiBUaGUgUyBsYW5ndWFnZSBpcyB2ZXJ5IG1hdHVyZS4NCjUuIFRoZSBtYWNoaW5lIGxlYXJuaW5nIGVudmlyb25tZW50IGluIFIgaXMgZXh0cmVtZWx5IHJpY2guDQoNCiMjIERvd25zaWRlcyB0byBtb2RlbGluZyBpbiBSDQoxLiAgUiBpcyBhIGRhdGEgYW5hbHlzaXMgbGFuZ3VhZ2UgYW5kIGlzIG5vdCBDIG9yIEphdmEuIElmIGEgaGlnaCBwZXJmb3JtYW5jZSBkZXBsb3ltZW50IGlzIHJlcXVpcmVkLCBSIGNhbiBiZSB0cmVhdGVkIGxpa2UgYSBwcm90b3R5cGluZyBsYW5ndWFnZS4NCjIuIFIgaXMgcyBtb3N0bHkgbWVtb3J5LWJvdW5kLiBUaGVyZSBhcmUgcGxlbnR5IG9mIGV4Y2VwdGlvbnMgdG8gdGhpcyB0aG91Z2guDQozLiBUaGUgbWFpbiBpc3N1ZSBpcyBvbmUgb2YgY29uc2lzdGVuY3kgb2YgaW50ZXJmYWNlLiANCg0KRm9yIGV4YW1wbGU6DQotIGhlcmUgYXJlIHR3byBtZXRob2RzIGZvciBzcGVjaWZ5aW5nIHdoYXQgdGVybXMgYXJlIGluIGEgbW9kZWwxLiBOb3QgYWxsIG1vZGVscyBoYXZlIGJvdGguDQotIDk5JSBvZiBtb2RlbCBmdW5jdGlvbnMgYXV0b21hdGljYWxseSBnZW5lcmF0ZSBkdW1teSB2YXJpYWJsZXMuDQotIFNwYXJzZSBtYXRyaWNlcyBjYW4gYmUgdXNlZCAodW5sZXNzIHRoZSBjYW4ndCkuDQoNCiMjIFN5bnRheCBmb3IgY29tcHV0aW5nIHByZWRpY3RlZCBjbGFzcyBwcm9iYWJpbGl0aWVzDQp8KipGdW5jdGlvbioqICB8ICoqUGFja2FnZSoqICAgICAgICAgICAgICAgICB8ICoqQ29kZSoqICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB8DQp8IDotLS0tLS0tLS0tLS18IDotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSB8IDotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSB8DQp8IGxkYSAgICAgICAgICB8IE1BU1MgICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaikgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB8DQp8IGdsbSAgICAgICAgICB8IHN0YXRzICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJyZXNwb25zZSIpICAgICAgICAgICB8DQp8IGdibSAgICAgICAgICB8IGdibSAgICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJyZXNwb25zZSIsIG4udHJlZXMpICB8DQp8IG1kYSAgICAgICAgICB8IG1kYSAgICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJwb3N0ZXJpb3IiKSAgICAgICAgICB8DQp8IHJwYXJ0ICAgICAgICB8IHJwYXJ0ICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJwcm9iIikgICAgICAgICAgICAgICB8DQp8IFdla2EgICAgICAgICB8IFJXZWthICAgICAgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJwcm9iYWJpbGl0eSIpICAgICAgICB8DQp8IGxvZ2l0Ym9vc3QgICB8IExvZ2l0Qm9vc3QgICAgICAgICAgICAgICAgICB8ICBwcmVkaWN0KG9iaiwgdHlwZSA9ICJyYXciLCBuSXRlcikgICAgICAgICB8DQoNCiMjIERpZmZlcmVudCBwaGlsb3NvcGhpZXMgdXNlZCBoZXJlDQpUaGVyZSBhcmUgdHdvIG1haW4gcGhpbG9zb3BoaWVzIHRvIGRhdGEgYW5hbHlzaXMgY29kZSB0aGF0IHdpbGwgYmUgZGlzY3Vzc2VkIGluIHRoaXMgd29ya3Nob3A6DQoNClRoZSBtYWluIHRyYWRpdGlvbmFsIGFwcHJvYWNoIHVzZXMgaGlnaC1sZXZlbCBzeW50YXggYW5kIGlzIHBlcmhhcHMgdGhlIG1vc3QgKip1bnRpZHkqKiBjb2RlIHRoYXQgeW91IHdpbGwgZW5jb3VudGVyLiANCg0KYGNhcmV0YCBpcyB0aGUgcHJpbWFyeSBwYWNrYWdlIGZvciB1bnRpZHkgcHJlZGljdGl2ZSBtb2RlbGluZzoNCjEuIE1vcmUgdHJhZGl0aW9uYWwgUiBjb2Rpbmcgc3R5bGUuDQoyLiBIaWdoLWxldmVsICJJIGRvIHRoYXQgZm9yIHlvdSIgc3ludGF4Lg0KMy4gTW9yZSBjb21wZXJlaGVuc2l2ZSAoZm9yIG5vdykgYW5kIGxlc3MgbW9kbHVsYXIuDQo0LiBDb250YWlucyBtYW55IG9wdGltaXphdGlvbnMgYW5kIGlzIGVhc2lseSBwYXJhbGxlbGl6ZWQuDQoNClRoZSAqdGlkeSogbW9kZWxpbmcgYXBwcm9hY2ggZXNwb3VzZXMgdGhlIHRlbmV0cyBvZiB0aGUgYHRpZHl2ZXJzZWANCjEuIFJldXNlcyBleGlzdGluZyBkYXRhIHN0cnVjdHVyZXMNCjIuIENvbXBvc2Ugc2ltcGxlIGZ1bmN0aW9ucyB3aXRoIHRoZSBwaXBlDQozLiBFbWJyYXNlIGZ1bmN0aW9uYWwgcHJvZ3JhbW1pbmcNCjQuIERlc2lnbiBmb3IgaHVtYW5zDQoNClRoaXMgYXBwcm9hY2ggaXMgZXhlbXBsaWZpZWQgYnkgcGFja2FnZXMgc3VjaCBhczoNCmBtb2RlbHJgLCBgYnJvb21gLCBgcmVjaXBlc2AsIGByc2FtcGxlYCwgYHlhcmRzdGlja2AgYW5kIGB0aWR5cG9zdGVyaW9yYC4NCg0KIyMgRXhhbXBsZSBkYXRhIHNldCAtIGhvdXNlIHByaWNlcw0KDQpGb3IgcmVncmVzc2lvbiBwcm9ibGVtcywgd2Ugd2lsbCB1c2UgdGhlIEFtZXMgSUEgaG91c2luZyBkYXRhLiANClRoZXJlIGFyZSAyLDkzMCBwcm9wZXJ0aWVzIGluIHRoZSBkYXRhLiANCg0KVGhlIHNhbGUgcHJpY2Ugd2FzIHJlY29yZGVkIGFsb25nIDgxIHByZWRpY3RvcnMsIGluY2x1ZGluZw0KLSBMb2NhdGlvbiAoZS5nLiBuZWlnaGJvcmhvb2QpIGFuZCBsb3QgaW5mb3JtYXRpb24uDQotIEhvdXNlIGNvbXBvbmVudHMgKGdhcmFnZSwgZmlyZXBsYWNlLCBwb29sLCBwb3JjaCwgZXRjLikuDQotIEdlbmVyYWwgYXNzZXNzbWVudHMgc3VjaCBhcyBvdmVyYWxsIHF1YWxpdHkgYW5kIGNvbmRpdGlvbi4NCi0gTnVtYmVyIG9mIGJlZHJvb21zLCBiYXRocywgYW5kIHNvIG9uLg0KDQpNb3JlIGRldGFpbHMgY2FuIGJlIGZvdW5kIGluIERlIENvY2sgKDIwMTEsIEpvdXJuYWwgb2YgU3RhdGlzdGljcyBFZHVjYXRpb24pLg0KDQpoZSByYXcgZGF0YSBhcmUgYXQgaHR0cDovL2JpdC5seS8yd2hnc1FNIGJ1dCB3ZSB3aWxsIHVzZSBhIHByb2Nlc3NlZCB2ZXJzaW9uIGZvdW5kIGluIHRoZSBgQW1lc0hvdXNpbmdgIHBhY2thZ2UuDQpgYGB7cn0NCmxpYnJhcnkoQW1lc0hvdXNpbmcpDQpBbWVzSG91c2luZzo6YW1lc19yYXcNCmBgYA0KDQpgYGB7cn0NCmxpYnJhcnkoQW1lc0hvdXNpbmcpDQphbWVzX2dlbyANCmBgYA0KDQoNCmBgYHtyIHdhcm5pbmc9RkFMU0UsIGVjaG89RkFMU0V9DQpsaWJyYXJ5KGxlYWZsZXQpDQoNCmxlYWZsZXQoKSAlPiUgDQogIGFkZFRpbGVzKCkgJT4lDQogIGFkZENpcmNsZU1hcmtlcnMoZGF0YT1hbWVzX2dlbywgcmFkaXVzPTMpDQogICMgYWRkTWFya2Vycyhsbmc9YW1lc19nZW8kTG9uZ2l0dWRlLCBsYXQ9YW1lc19nZW8kTGF0aXR1ZGUpDQpgYGANCg0KIyMgRXhhbXBsZSBkYXRhIHNldCAtIEZ1ZWwgZWNvbm9teQ0KDQpUaGUgZGF0YSB0aGF0IGFyZSB1c2VkIGhlcmUgYXJlIGFuIGV4dGVuZGVkIHZlcnNpb24gb2YgdGhlIHViaXF1aXRvdXMgYG10Y2Fyc2AgZGF0YSBzZXQuIFtmdWVsZWNvbm9teS5nb3ZdKGh0dHBzOi8vd3d3LmZ1ZWxlY29ub215Lmdvdi9mZWcvZG93bmxvYWQuc2h0bWwpIHdhcyB1c2VkIHRvIG9idGFpbiBmdWVsIGVmZmljaWVuY3kgZGF0YSBvbiBjYXJzIGZyb20gMjAxNS0xOC4NCg0KT3ZlciB0aGlzIHRpbWUgcmFuZ2UsIGR1cGxpY2F0ZSByYXRpbmdzIHdlcmUgZWxpbWluYXRlZDsgdGhlc2Ugb2NjdXIgd2hlbiB0aGUgc2FtZSBjYXIgaXMgc29sZCBmb3Igc2V2ZXJhbCB5ZWFycyBpbiBhIHJvdy4gQXMgYSByZXN1bHQsIHRoZXJlIGFyZSAzMjk0IGNhcnMgdGhhdCBhcmUgbGlzdGVkIGluIHRoZSBkYXRhLiBUaGUgcHJlZGljdG9ycyBpbmNsdWRlIHRoZSBhdXRvbWFrZXIgYW5kIGFkZGl0aW9uIGluZm9ybWF0aW9uIGFib3V0IHRoZSBjYXJzIChlLmcuIGludGFrZSB2YWx2ZXMgcGVyIGN5Y2xlLCBhc3BpcmF0aW9uIG1ldGhvZCwgZXRjKS4NCg0KSW4gb3VyIGFuYWx5c2lzLCB0aGUgZGF0YSBmcm9tIDIwMTUtMjAxNyBhcmUgdXNlZCBmb3IgdHJhaW5pbmcgdG8gc2VlIGlmIHdlIGNhbiBwcmVkaWN0IHRoZSA2MDkgY2FycyB0aGF0IHdlcmUgbmV3IGluIDIwMTguDQoNClRoZXNlIGRhdGEgYXJlIHN1cHBsaWVkIGluIHRoZSBHaXRIdWIgcmVwby4NCg0KIyMgRXhhbXBsZSBkYXRhIHNldCAtIFByZWRpY3RpbmcgcHJvZmVzc2lvbg0KT2tDdXBpZCBpcyBhbiBvbmxpbmUgZGF0YSBzaXRlIHRoYXQgc2VydmVzIGludGVybmF0aW9uYWwgdXNlcnMuIEtpbSBhbmQgRXNjb2JlZG8tTGFuZCAoMjAxNSwgSm91cm5hbCBvZiBTdGF0aXN0aWNzIEVkdWNhdGlvbikgZGVzY3JpYmUgYSBkYXRhIHNldCB3aGVyZSBvdmVyIDUwLDAwMCBwcm9maWxlcyBmcm9tIHRoZSBTYW4gRnJhbnNpc2NvIGFyZWEgd2VyZSBtYWRlIGF2YWlsYWJsZSBieSB0aGUgY29tcGFueS4NCg0KVGhlIGRhdGEgY29udGFpbnMgc2V2ZXJhbCB0eXBlcyBvZiBmaWVsZHM6DQoNCi0gYSBudW1iZXIgb2Ygb3BlbiB0ZXh0IGVzc2F5cyByZWxhdGVkIHRvIGludGVyZXN0cyBhbmQgcGVyc29uYWwgZGVzY3JpcHRpb25zDQotIHNpbmdsZSBjaG9pY2UgdHlwZSBmaWVsZHMsIHN1Y2ggYXMgcHJvZmVzc2lvbiwgZGlldCwgZ2VuZGVyLCBib2R5IHR5cGUsIGV0Yy4NCi0gbXVsdGlwbGUgY2hvaWNlIGRhdGEsIGluY2x1ZGluZyBsYW5ndWFnZXMgc3Bva2VuLCBldGMuDQotICoqbm8qKiB1c2VybmFtZXMgb3IgcGljdHVyZXMgd2VyZSBpbmNsdWRlZC4NCg0KV2Ugd2lsbCB0cnkgdG8gcHJlZGljdCB3aGV0aGVyIHNvbWVvbmUgaGFzIGEgcHJvZmVzc2lvbiBpbiB0aGUgU1RFTSBmaWVsZHMgKHNjaWVuY2UsIHRlY2hub2xvZ3ksIGVuZ2luZWVyaW5nLCBhbmQgbWF0aCkgdXNpbmcgYSByYW5kb20gc2FtcGxlIG9mIHRoZSBvdmVyYWxsIGRhdGFzZXQuDQoNCiMjIFRpZHl2ZXJzZSBzeW50YXgNCk1hbnkgdGlkeXZlcnNlIGZ1bmN0aW9ucyBoYXZlIHN5bnRheCB1bmxpa2UgYmFzZSBSIGNvZGUuIEZvciBleGFtcGxlOg0KDQotIHZlY3RvcnMgb2YgdmFyaWFibGUgbmFtZXMgYXJlIGVzY2hld2VkIGluIGZhdm9yIG9mICpmdW5jdGlvbmFsIHByb2dyYW1taW5nKi4gRm9yIGV4YW1wbGU6DQpgYGB7ciB3YXJuaW5nPUZBTFNFLCBldmFsPUZBTFNFfQ0KY29udGFpbnMoIlNlcGFsIikNCg0KIyBpbnN0ZWFkIG9mDQpjKCJTZXBhbC5XaWR0aCIsICJTZXBhbC5MZW5ndGgiKQ0KYGBgDQoNCi0gVGhlICpwaXBlKiBvcGVyYXRvciBpcyBwcmVmZXJyZWQuIEZvciBleGFtcGxlOg0KYGBge3IgZXZhbD1GQUxTRX0NCm1lcmdlZCA8LSBpbm5lcl9qb2luKGEsIGIpDQojIGlzIGVxdWFsIHRvDQptZXJnZWQgPC0gYSAlPiUNCiAgaW5uZXJfam9pbihiKQ0KYGBgDQoNCi0gRnVuY3Rpb25zIGFyZSBtb3JlICptb2R1bGFyKiB0aGFuIHRoZWlyIHRyYWRpdGlvbmFsIGFuYWxvZ3MgKGBkcGx5cmAncyBgZmlsdGVyYCBhbmQgYHNlbGVjdGAgVlMgYGJhc2U6OnN1YnNldGApLg0KDQojIyBTb21lIGV4YW1wbGUgZGF0YSBtYW5pcHVsYXRpb24gY29kZQ0KYGBge3IgZXZhbD1GQUxTRX0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KDQphbWVzIDwtIHJlYWRfZGVsaW0oImh0dHA6Ly9iaXQubHkvMndoZ3NRTSIsIGRlbGltID0gIlx0IikgJT4lDQogIHJlbmFtZV9hdCh2YXJzKGNvbnRhaW5zKCcgJykpLCBmdW5zKGdzdWIoJyAnLCAnXycsIC4pKSkgJT4lDQogIHJlbmFtZShTYWxlX1ByaWNlID0gU2FsZVByaWNlKSAlPiUNCiAgZmlsdGVyKCFpcy5uYShFbGVjdHJpY2FsKSkgJT4lDQogIHNlbGVjdCgtT3JkZXIsIC1QSUQsIC1HYXJhZ2VfWXJfQmx0KQ0KYGBgDQoNCmBgYHtyfQ0KDQpsaWJyYXJ5KCkNCg0KYW1lcyA8LSBhbWVzX3JhdyAlPiUgDQogIHJlbmFtZV9hdCh2YXJzKGNvbnRhaW5zKCcgJykpLCBmdW5zKGdzdWIoJyAnLCAnXycsIC4pKSkgJT4lDQogIHJlbmFtZShTYWxlX1ByaWNlPVNhbGVQcmljZSkgJT4lIA0KICBmaWx0ZXIoIWlzLm5hKEVsZWN0cmljYWwpKSAlPiUgDQogIHNlbGVjdCgtT3JkZXIsLVBJRCwgLUdhcmFnZV9Zcl9CbHQpDQogIA0KICANCmFtZXMgJT4lIA0KICBncm91cF9ieShBbGxleSkgJT4lIA0KICBzdW1tYXJpemUobWVhbl9wcmljZT1tZWFuKFNhbGVfUHJpY2UvMTAwMCksDQogICAgICAgICAgICBuPXN1bSghaXMubmEoU2FsZV9QcmljZSkpKQ0KYGBgDQoNCiMjIEV4YW1wbGUgYGdncGxvdDJgIGNvZGUNCmBgYHtyfQ0KbGlicmFyeShnZ3Bsb3QyKQ0KDQpnZ3Bsb3QoYW1lcywNCiAgICAgICBhZXMoeD1HYXJhZ2VfVHlwZSwNCiAgICAgICAgICAgeT1TYWxlX1ByaWNlKSkrDQogIGdlb21fdmlvbGluKCkrDQogIGNvb3JkX3RyYW5zKHk9ImxvZzEwIikrDQogIHhsYWIoIkdhcmFnZSBUeXBlIikrDQogIHlsYWIoIlNhbGUgUHJpY2UiKQ0KYGBgDQoNCiMjIEV4YW1wbGVzIG9mIGBwdXJycjo6bWFwKmANCg0KYGBge3J9DQpsaWJyYXJ5KHB1cnJyKQ0KDQojIFN1bW1hcml6ZSB2aWEgcHVycnI6Om1hcA0KYnlfYWxsZXkgPC0gc3BsaXQoYW1lcywgYW1lcyRBbGxleSkNCmlzX2xpc3QoYnlfYWxsZXkpDQojIGdsaW1wc2UoYnlfYWxsZXkpDQpgYGANCg0KYGBge3J9DQptYXAoYnlfYWxsZXksIG5yb3cpDQpgYGANCg0KYGBge3J9DQptYXBfaW50KGJ5X2FsbGV5LCBucm93KQ0KYGBgDQoNCmBgYHtyfQ0KIyB3b3JrIG9uIG5vLWxpc3QgdmVjdG9ycyB0b28NCmFtZXMgJT4lIA0KICBtdXRhdGUoU2FsZV9QcmljZT1TYWxlX1ByaWNlICU+JSANCiAgICAgICAgICAgbWFwX2RibChmdW5jdGlvbih4KXgvMTAwMCkpICU+JSANCiAgc2VsZWN0KFNhbGVfUHJpY2UsIFlyX1NvbGQpICU+JSANCiAgaGVhZCgpDQpgYGANCg0KIyMgUXVpY2sgZGF0YSBpbnZlc3RpZ2F0aW9uDQpUbyBnZXQgd2FybWVkIHVwLCBsZXQncyBsb2FkIHRoZSBBbWVzIGRhdGEgYW5kIGRvIHNvbWUgYmFzaWMgaW52ZXN0aWdhdGlvbnMgaW50byB0aGUgdmFyaWFibGVzLCBzdWNoIGFzIGV4cGxvcmF0b3J5IHZpc3VhbGl6YXRpb25zIG9yIHN1bW1hcnkgc3RhdGlzdGljcy4gVGhlIGlkZWEgaXMgdG8gZ2V0IGEgZmVlbCBmb3IgdGhlIGRhdGEuDQpgYGB7cn0NCmxpYnJhcnkoQW1lc0hvdXNpbmcpDQphbWVzIDwtIG1ha2VfYW1lcygpDQpgYGANCg0KDQojIyBXaGVyZSB3ZSBnbyBmcm9tIGhlcmUNCg0KKipQYXJ0IDIqKiBCYXNpYyBQcmluY2lwbGVzDQotIERhdGEgU3BsaXR0aW5nLCBNb2RlbHMgaW4gUiwgUmVzYW1wbGluZywgVHVuaW5nKGByc2FtcGxlYCkNCg0KKipQYXJ0IDMqKiBGZWF0dXJlIGVuZ2luZWVyaW5nIHByZXByb2Nlc3NpbmcNCi0gRGF0YSB0cmVhdG1lbnQgKGByZWNpcGVzYCkNCg0KKipQYXJ0IDQqKiBSZWdyZXNzaW9uIE1vZGVsaW5nDQotIE1lYXN1cmluZyBQZXJmb3JtYW5jZSwgcGVuYWxpemVkIHJlZ3Jlc3Npb24sIG11bHRpdmFyaWF0ZSBhZGFwdGl2ZSByZWdyZXNzaW9uIHNwbGluZXMgKE1BUlMpLCBlbnNlbWJsZXMgKGB5YXJkc3RpY2tgLCBgcmVjaXBlc2AsIGBjYXJldGAsIGBlYXJ0aGAsIGBnbG1uZXRgLCBgdGlkeXBvc3RlcmlvcmAsIGBkb1BhcmFsbGVsYCkNCg0KKipQYXJ0IDUqKiBDbGFzc2lmaWNhdGlvbiBNb2RlbGluZw0KLSBNZWFzdXJpbmcgUGVyZm9ybWFuY2UsIHRyZWVzLCBlbnNlbWJsZXMsIG5haXZlIEJheWVzIChgeWFyZHN0aWNrYCwgYHJlY2lwZXNgLCBgY2FyZXRgLCBgcnBhcnRgLCBga2xhUmAsIGB0aWR5cG9zdGVyaW9yYCkNCg0KIyMgUmVzb3VyY2VzDQpodHRwOi8vd3d3LnRpZHl2ZXJzZS5vcmcvDQpbUiBmb3IgRGF0YSBTY2llbmNlXShodHRwOi8vcjRkcy5oYWQuY28ubnovKQ0KW0plbm55J3MgcHVycnIgdHV0b3JpYWxdKGh0dHBzOi8vamVubnliYy5naXRodWIuaW8vcHVycnItdHV0b3JpYWwvKSBvciBbSGFwcHkgUiBVc2VycyBQdXJycl0oaHR0cHM6Ly93d3cucnN0dWRpby5jb20vcmVzb3VyY2VzL3ZpZGVvcy9oYXBweS1yLXVzZXJzLXB1cnJyLXR1dG9yaWFsLykNCltQcm9ncmFtbWluZyB3aXRoIGRwbHlyIHZpZ25ldHRlXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvZHBseXIvdmlnbmV0dGVzL3Byb2dyYW1taW5nLmh0bWwpDQpbU2VsdmEgUHJhYmhha2FyYW4ncyBnZ3Bsb3QyIHR1dG9yaWFsXShodHRwOi8vci1zdGF0aXN0aWNzLmNvL0NvbXBsZXRlLUdncGxvdDItVHV0b3JpYWwtUGFydDEtV2l0aC1SLUNvZGUuaHRtbCkNCltjYXJldCBwYWNrYWdlIGRvY3VtZW50YXRpb25dKGh0dHBzOi8vdG9wZXBvLmdpdGh1Yi5pby9jYXJldC8pDQpbQ1JBTiBNYWNoaW5lIExlYXJuaW5nIFRhc2sgVmlld10oaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3ZpZXdzL01hY2hpbmVMZWFybmluZy5odG1sKQ0KDQpBYm91dCB0aGVzZSBzbGlkZXMuLi4uIHRoZXkgd2VyZSBjcmVhdGVkIHdpdGggWWlodWkncyB4YXJpbmdhbiBhbmQgdGhlIHN0eWxpbmdzIGFyZSBhIHNsaWdodGx5IG1vZGlmaWVkIHZlcnNpb24gb2YgUGF0cmljayBTY2hyYXR6J3MgTWV0cm9wb2xpcyB0aGVtZS4NCg0KIyBQYXJ0MiBCYXNpYyBwcmluY2lwbGVzDQoNCiMjIEludHJvZHVjdGlvbg0KSW4gdGhpcyBzZWN0aW9uLCB3ZSB3aWxsIGludHJvZHVjZSBjb25jZXB0cyB0aGF0IGFyZSB1c2VmdWwgZm9yIGFueSB0eXBlIG9mIG1hY2hpbmUgbGVhcm5pbmcgbW9kZWw6DQotIG1vZGVsaW5nIHZlcnN1cyB0aGUgbW9kZWwNCi0gZGF0YSBzcGxpdHRpbmcNCi0gcmVzYW1wbGluZw0KLSB0dW5pbmcgcGFyYW1ldGVycyBhbmQgb3ZlcmZpdHRpbmcNCi0gbW9kZWwgdHVuaW5nDQoNCk1hbnkgb2YgdGhlc2UgdG9waWNzIHdpbGwgYmUgcHV0IGludG8gYWN0aW9uIGluIGxhdGVyIHNlY3Rpb25zLg0KDQojIyMgVGhlIG1vZGVsaW5nIHByb2Nlc3MNCkNvbW1vbiBzdGVwcyBkdXJpbmcgbW9kZWwgYnVpbGRpbmcgYXJlOg0KDQotIGVzdGltYXRpbmcgbW9kZWwgcGFyYW1ldGVycyAoaS5lLiwgdHJhaW5pbmcgbW9kZWxzKQ0KLSBkZXRlcm1pbmluZyB0aGUgdmFsdWVzIG9mICp0dW5pbmcgcGFyYW1ldGVycyogdGhhdCBjYW5ub3QgYmUgZGlyZWN0bHkgY2FsY3VsYXRlZCBmcm9tIHRoZSBkYXRhDQotIG1vZGVsIHNlbGVjdGlvbiAod2l0aGluIGEgbW9kZWwgdHlwZSkgYW5kIG1vZGVsIGNvbXBhcmlzb24gKGJldHdlZW4gdHlwZXMpDQotIGNhbGN1bGF0aW5nIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgZmluYWwgbW9kZWwgdGhhdCB3aWxsIGdlbmVyYWxpemUgdG8gbmV3IGRhdGENCg0KTWFueSBib29rcyBhbmQgY291cnNlIHBvcnRyYXkgcHJlZGljdGl2ZSBtb2RlbGluZyBhcyBhIHNob3J0IHNwcmludC4gQSBiZXR0ZXIgYW5hbG9neSB3b3VsZCBiZSBhIG1hcmF0aG9uIG9yIGNhbXBhaWduIChkZXBlbmRpbmcgb24gaG93IGhhcmQgdGhlIHByb2JsZW0gaXMpLg0KDQojIyMgV2hhdCB0aGUgbW9kZWluZyBwcm9jZXNzIHVzdWFsbHkgbG9vayBsaWtlDQpgYGB7cn0NCmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJDOi9Vc2Vycy9rb2ppa20ubWl6dW11cmEvRGVza3RvcC9EYXRhIFNjaWVuY2UvVXNlUiAyMDE4L0FwcGxpZWQgTUwvaW50cm8tcHJvY2Vzcy0xLnBuZyIpDQpgYGANCg0KIyMgRGF0YSB1c2FnZQ0KIyMjIERhdGEgU3BsaXR0aW5nIGFuZCBzcGVuZGluZw0KDQpIb3cgZG8gd2UgInNwZW5kIiB0aGUgZGF0YSB0byBmaW5kIGFuIG9wdGltYWwgbW9kZWw/DQpXZSB0eXBpY2FsbHkgc3BsaXQgZGF0YSBpbnRvIHRyYWluaW5nIGFuIHRlc3QgZGF0YSBzZXRzOg0KDQotICoqVHJhaW5pbmcgc2V0Kio6IHRoZXNlIGRhdGEgYXJlIHVzZWQgdG8gZXN0aW1hdGUgbW9kZWwgcGFyYW1ldGVycyBhbmQgcGljayB0aGUgdmFsdWVzIG9mIHRoZSBjb21wbGV4aXR5IHBhcmFtZXRlcihzKSBmb3IgdGhlIG1vZGVsLg0KLSAqKlRlc3Qgc2V0Kio6IHRoZXNlIGRhdGEgY2FuIGJlIHVzZWQgdG8gZ2V0IGFuIGluZGVwZW5kZW50IGFzc2Vzc21lbnQgb2YgbW9kZWwgZWZmaWNhY3kuIFRoZXkgc2hvdWxkIG5vdCBiZSB1c2VkIGR1cmluZyBtb2RlbCB0cmFpbmluZy4gDQoNClRoZSBtb3JlIGRhdGEgd2Ugc3BlbmQsIHRoZSBiZXR0ZXIgZXN0aW1hdGVzIHdlJ2xsIGdldCAocHJvdmlkZWQgdGhlIGRhdGEgaXMgYWNjdXJhdGUpLiANCg0KR2l2ZW4gYSBmaXhlZCBhbW91bnQgb2YgZGF0YToNCi0gdG9vIG11Y2ggc3BlbnQgaW4gdHJhaW5pbmcgd29uJ3QgYWxsb3cgdXMgdG8gZ2V0IGEgZ29vZCBhc3Nlc3NtZW50IG9mIHByZWRpY3RpdmUgcGVmb3JtYW5jZS4gV2UgbWF5IGZpbmQgYSBtb2RlbCB0aGF0IGZpdHMgdGhlIHRyYWluaW5nIGRhdGEgdmVyeSB3ZWxsLCBidXQgaXMgbm90IGdlbmVyYWxpemFibGUgKG92ZXJmaXR0aW5nKQ0KLSB0b28gbXVjaCBzcGVudCBpbiB0ZXN0aW5nIHdvbid0IGFsbG93IHVzIHRvIGdldCBhIGdvb2QgYXNzZXNzbWVudCBvZiBtb2RlbCBwYXJhbWV0ZXJzDQoNClN0YXRpc3RpY2FsbCx5IHRoZSBlc3QgY291cnNlIG9mIGFjdGlvbiB3b3VsZCBiZSB1c2UgYWxsIHRoZSBkYXRhIGZvciBtb2RlbCBidWlsZGluZyBhbmQgdXNlIHN0YXRpc3RpY2FsIG1ldGhvZHMgdG8gZ2V0IGVzdGltYXRlcyBvZiBlcnJvci4NCg0KRnJvbSBhIG5vbi1zdGF0aXN0aWNhbCBwZXJzcGVjdGl2ZSwgbWFueSBjb25zbWVycyBvZiBjb21wbGV4IG1vZGVscyBlbXBoYXNpemUgdGhlIG5lZWQgZm9yIHVudG91Y2hlZCBzZXQgb2Ygc2FtcGxlZCB0byBldmFsdWF0ZSBwZXJmb3JtYW5jZS4NCg0KIyMjIExhcmdlIGRhdGEgc2V0DQpXaGVuIGEgbGFyZ2UgYW1vdW50IG9mIGRhdGEgYXJlIGF2YWlsYWJsZSwgaXQgbWlnaHQgc2VlbSBsaWtlIGEgZ29vZCBpZGVhIHRvIHB1dCBhIGxhcmdlIGFtb3VudCBpbnRvIHRoZSB0cmFpbmluZyBzZXQuICpQZXJzb25hbGx5KiwgSSB0aGluayB0aGF0IHRoaXMgY2F1c2VzIG1vcmUgdHJvdWJsZSB0aGFuIGl0IGlzIHdvcnRoIGR1ZSB0byBkaW1pbmlzaGluZyByZXR1cm5zIG9uIHBlcmZvcm1hbmNlIGFuZCB0aGUgYWRkZWQgY29zdCBhbmQgY29tcGV4aXR5IG9mIHRoZSByZXF1aXJlZCBpbmZyYXN0cnVjdHVyZS4NCg0KQWx0ZXJuYXRpdmVseSwgaXQgaXMgcHJvYmFibHkgYSBiZXR0ZXIgaWRlYSB0byByZXNlcnZlIGdvb2QgcGVyY2VudGFnZXMgb2YgdGhlIGRhdGEgZm9yIHNwZWNpZmljIHBhcnRzIG9mIHRoZSBtb2RlbGluZyBwcm9jZXNzLiBGb3IgZXhhbXBsZTogDQoNCi0gU2F2ZSBhIGxhcmdlIGNodW5rIG9mIGRhdGEgdG8gcGVyZm9ybSBmZWF0dXJlIHNlbGVjdGlvbiBwcmlvciB0byBtb2RlbCBidWlsZGluZw0KLSBSZXRhaW4gZGF0YSB0byBjYWxpYnJhcmF0ZSBjbGFzcyBwcm9iYWJpbGl0aWVzIG9yIGRldGVybWluZSBhIGN1dG9mZiB2aWEgYW4gUk9DIGN1cnZlLiANCg0KQWxzbyB0aGVyZSBtYXkgYmUgbGl0dGxlIG5lZWQgZm9yIGl0ZXJhdGl2ZSByZXNhbXBsaW5nIG9mIHRoZSBkYXRhLiBBIHNpbmdsZSBob2xkb3V0IChha2EgdmFsaWRhdGlvbiBzZXQpIG1heSBiZSBzdWZmaWNpZW50IGluIHNvbWUgY2FzZXMgaWYgdGhlIGRhdGEgYXJlIGxhcmdlIGVub3VnaCBhbmQgdGhlIGRhdGEgc2FtcGxpbmcgbWVjaGFuaXNtIGlzIHNvbGlkLg0KDQoNCiMjIyBNZWNoYW5pcyBvZiBkYXRhIHNwbGl0dGluZw0KDQpUaGVyZSBhcmUgYSBmZXcgZGlmZmVyZW50IHdheXMgdG8gZG8gdGhlIHNwbGl0OiBzaW1wbGUgcmFuZG9tIHNhbXBsaW5nLCBzdHJhdGlmaWVkIHNhbXBsaW5nIGJhc2VkIG9uIHRoZSBgb3V0Y29tZWAsIGJ5IGBkYXRlYCwgb3IgYG1ldGhvZHNgIHRoYXQgZm9jdXMgb24gdGhlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgcHJlZGljdG9ycy4NCg0KRm9yIHN0cmF0aWZpY2F0aW9uOg0KLSAqKmNsYXNzaWZpY2F0aW9uKio6IHRoaXMgd291bGQgbWVhbiBzYW1wbGluZyB3aXRoaW4gdGhlIGNsYXNzZXMgYXMgdG8gcHJlc2VydmUgdGhlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgb3V0Y29tZSBpbiB0aGUgdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cw0KLSAqKnJlZ3Jlc3Npb24qKjogZGV0ZXJtaW5lIHRoZSBxdWFydGlsZXMgb2YgdGhlIGRhdGEgc2V0IGFuZCBzYW1wbGVzIHdpdGhpbiB0aG9zZSBhcnRpZmljaWFsIGdyb3Vwcw0KDQojIyMgQW1lcyBIb3VzaW5nIGRhdGENCmBgYHtyfQ0KYW1lcyA8LSBtYWtlX2FtZXMoKQ0KZGltKGFtZXMpDQpgYGANCg0KYGBge3Igd2FybmluZz1GQUxTRX0NCmxpYnJhcnkocnNhbXBsZSkNCg0KIyBtYWtlIHN1cmV0IHlvdSBnZXQgdGhlIHNhbWUgcmFuZG9tIG51bWJlcnMNCnNldC5zZWVkKDQ1OTUpDQoNCmRhdGFfc3BsaXQgPC1pbml0aWFsX3NwbGl0KGFtZXMsc3RyYXRhPSJTYWxlX1ByaWNlIikgDQoNCmFtZXNfdHJhaW4gPC0gdHJhaW5pbmcoZGF0YV9zcGxpdCkNCmFtZXNfdGVzdCA8LSB0ZXN0aW5nKGRhdGFfc3BsaXQpDQoNCm5yb3coYW1lc190cmFpbikvbnJvdyhhbWVzKQ0KYGBgDQoNCiMjIyBPdXRjb21lIGRpc3RyaWJ1dGlvbg0KYGBge3J9DQpsaWJyYXJ5KGdncGxvdDIpDQoNCiMgRG8gdGhlIGRpc3RyaWJ1dGlvbiBsaW5lLXVwPw0KZ2dwbG90KGFtZXNfdHJhaW4sYWVzKHg9U2FsZV9QcmljZSkpKw0KICAgZ2VvbV9saW5lKHN0YXQgPSAiZGVuc2l0eSIsIA0KICAgICAgICAgICAgdHJpbSA9IFRSVUUpICsgDQogIGdlb21fbGluZShkYXRhID0gYW1lc190ZXN0LCANCiAgICAgICAgICAgIHN0YXQgPSAiZGVuc2l0eSIsIA0KICAgICAgICAgICAgdHJpbSA9IFRSVUUsIGNvbCA9ICJyZWQiKQ0KYGBgDQoNCiMjIENyZWF0aW5nIG1vZGVscyBpbiBSDQojIyMgU3BlY2lmeWluZyBtb2RlbHMgaW4gUiB1c2luZyBmb3JtdWxhcw0KVG8gZml0IGEgbW9kZWwgdG8gdGhlIGhvdXNpbmcgZGF0YSwgdGhlIG1vZGVsIHRlcm1zIG11c3QgYmUgc3BlY2lmaWVkLiBIaXN0b3JpY2FsbHksIHRoZXJlIGFyZSB0d28gbWFpbiBpbnRlcmZhY2VzIGZvciBkb2luZyB0aGlzLiANCg0KVGhlIGZvbXVsYSBpbnRlcmZhY2UgdXNpbmcgUiBbZm9tdWxhIHJ1bGVzXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy9kb2MvbWFudWFscy9yLXJlbGVhc2UvUi1pbnRyby5odG1sI0Zvcm11bGFlLWZvci1zdGF0aXN0aWNhbC1tb2RlbHMpIHRvIHNwZWNpZnkgYSBzeW1ib2xpYyByZXByZXNlbnRhdGlvbiBvZiB0aGUgdGVybXMgYW5kIHZhcmlhYmxlcy4gRm9yIGV4YW1wbGU6DQpgYGByDQpmb28oU2FsZV9QcmljZSB+IE5laWdodGJvcmhvb2QgKyBZZWFyX1NvbGQgKyBOZWlnaGJvcmhvb2Q6WWVhcl9Tb2xkLCBkYXRhPWFtZXNfdHJhaW4pDQpgYGANCg0KT1IgDQoNCmBgYHINCmZvbyhTYWxlX1ByaWNlfi4sIGRhdGE9YW1lc190cmFpbikNCmBgYA0KDQpPUiANCmBgYHINCmZvbyhsb2cxMChTYWxlX1ByaWNlKX5ucyhMb25naXR1ZGUsIGRmPTMpK25zKExhdGl0dWRlLGRmPTMpLGRhdGE9YW1lc190cmFpbikNCmBgYA0KDQpUaGlzIGlzIHZlcnkgY29udmVuaWVudCBidXQgaXQgaGFzIHNvbWUgZGlzYWR2YW50YWdlcy4NCg0KIyMjIERvd25zaWRlcyB0byBmb3JtdWxhcw0KLSBZb3UgY2FuJ3QgbmVzdCBpbi1saW5lIGZ1bmN0aW9ucyBzdWNoIGFzIGBmb28oeSB+IHBjYShzY2FsZSh4MSksIHNjYWxlKHgyKSwgc2NhbGUoeDMpKSwgZGF0YSA9ZGF0KWAuDQotIEFsbCB0aGUgbW9kZWwgbWF0cml4IGNhbGN1bGF0aW9ucyBoYXBwZW4gYXQgb25jZSBhbmQgY2FuJ3QgYmUgcmVjeWNsZWQgd2hlbiB1c2VkIGluIGEgbW9kZWwgZnVuY3Rpb24uIA0KLSBGb3IgdmVyeSAqd2lkZSogZGF0YSBzZXRzLCB0aGUgZm9ybXVsYSBtZXRob2QgY2FuIGJlIGV4dHJlbWVseSBpbmVmZmljaWVudC4NCi0gVGhlcmUgYXJlIGxpbWl0ZWQgKnJvbGVzKiB0aGF0IHZhcmlhYmxlcyBjYW4gdGFrZSB3aGljaCBoYXMgbGVkIHRvIHNldmVyYWwgcmUtaW1wZW1lbnRhdGlvbnMgb2YgZm9ybXVsYXMuDQotIFNwZWNpZnluZyBtdWx0aXZhcml0ZSBvdXRjb21lcw0KLSBOb3QgYWxsIG1vZGVsIGZ1bmN0aW9ucyBoYXZlIGEgZm9ybXVsYSBtZXRob2QuDQoNCiMjIyBTcGVjaWZ5aW5nIG1vZGVsIHdpdGhvdXQgZm9ybXVsYXMNClNvbWUgbW9kZWxpbmcgZnVuY3Rpb24gaGF2ZSB0aGUgbm9uLWZvcm11bGEgaW50ZXJmYWNlLiBUaGlzIHVzdWFsbHkgaGFzIGFyZ3VtZW50cyBmb3IgdGhlIHByZWRpY3RvcnMgYW5kIHRoZSBvdXRjb21lKHMpOg0KYGBgcg0KIyBVc3VhbGx5LCB0aGUgdmFyaWFibGUgbXVzdCBhbGwgYmUgbnVtZXJpYw0KDQpwcmVfdmFycyA8LSBjKCJZZWFyX1NvbGQiLCJMb25naXR1ZGUiLCJMYXRpdHVkZSIpDQpmb28oeD1hbWVzX3RyYWluWyxwcmVfdmFyc10sDQogICAgeT1hbWVzX3RyYWluJFNhbGVfUHJpY2UpDQpgYGANCg0KVGhpcyBpcyBpbmNvbnZlbmllbnQgaWYgeW91IGhhdmUgdHJhbnNmb3JtYXRpb25zLCBmYWN0b3IgdmFyaWFibGVzLCBpbnRlcmFjdGlvbnMgb3IgYW55IG90aGVyIG9wZXJhdGlvbnMgYXBwbHkgcHJpb3IgdG8gbW9kZWxpbmcuIA0KDQpPdmVyYWxsLCBpdCBpcyBkaWZmaWN1bHQgdG8gcHJlZGljdCBpZiBhIHBhY2thZ2UgaGFzIG9uZSBvciBib3RoIG9mIHRoZXNlIGludGVyZmFjZXMuIEZvciBleGFtcGxlLCBgbG1gIG9ubHkgaGFzIGZvcm11bGFzLiANCg0KVGhlcmUgaXMgYSAqKnRoaXJkIGludGVyZmFjZSoqIHVzaW5nICpyZWNpcGVzKiB0aGF0IHdpbGwgYmUgZGlzY3Vzc2VkIGxhdGVyIHRoYXQgc29sdmUgc29tZSBvZiB0aGVzZSBpc3N1ZXMuDQoNCiMjIyBBIGxpbmVhciByZWdyZXNzaW9uIG1vZGVsDQpMZXQncyBzdGFydCBieSBmaXR0aW5nIGFuIG9yZGluYXJ5IGxpbmVhciByZWdyZXNzaW9uIG1vZGVsIHRvIHRoZSB0cmFpbmluZyBzZXQuIFlvdSBjYW4gY2hvb3NlIHRoZSBtb2RlbCB0ZXJtcyBmb3IgeW91ciBtb2RlbCBidXQgSSB3aWxsIHVzZSBhIHZlcnkgc2ltcGxlIG1vZGVsOg0KYGBge3J9DQpoZWFkKGFtZXNfdHJhaW4pDQoNCg0Kc2ltcGxlX2xtIDwtIGxtKGxvZzEwKFNhbGVfUHJpY2UpfkxvbmdpdHVkZStMYXRpdHVkZSwgZGF0YT1hbWVzX3RyYWluKQ0KYGBgDQoNCkJlZm9yZSBsb29raW5nIGF0IGNvZWZmaWNpZW50cywgd2Ugc2hvdWxkIGRvIHNvbWUgbW9kZWwgY2hlY2tpbmcgdG8gc2VlIGlmIHRoZXJlIGlzIGFueXRoaW5nIG9idmlvdXNseSB3cm9uZyB3aXRoIHRoZSBtb2RlbC4NCg0KVG8gZ2V0IHRoZSBzdGF0aXN0aWNzIG9uIHRoZSBpbmRpdmlkdWFsIHBvaW50cywgd2Ugd2lsbGwgdXNlIHRoZSBhd2Vzb21lIGBicm9vbWAgcGFja2FnZToNCmBgYHtyfQ0KbGlicmFyeShicm9vbSkNCmxpYnJhcnkobWFncml0dHIpDQoNCnNpbXBsZV9sbV92YWx1ZXMgPC0gYXVnbWVudChzaW1wbGVfbG0pDQpzaW1wbGVfbG1fdmFsdWVzICU+JSBuYW1lcygpDQpgYGANCg0KIyMjIEhhbmRzLW9uOiBzb21lIGJhc2ljIGRpYWdub3N0aWNzDQpGcm9tIHRoZXNlIHJlc3VsdHMsIGxldCdzIGRvIHNvbWUgdmlzdWFsaXphdGlvbnM6DQoNCi0gUGxvdCB0aGUgb2JzZXJ2ZWQgdmVyc3VzIGZpdHRlZCB2YWx1ZXMNCi0gUGxvdCB0aGUgcmVzaWR1YWxzDQotIFBsb3QgdGhlIHByZWRpY3RlZCB2ZXJzdXMgcmVzZGlkdWFscw0KDQpBcmUgdGhlcmUgYW55IGRvd25zaWRlcyB0byB0aGlzIGFwcHJvYWNoPw0KDQojIyBNb2RlbCBldmFsdWF0aW9uDQojIyMgT3ZlcmFsbCBtb2RlbCBzdGF0aXN0aWNzDQpJZiB5b3UgdXNlIHRoZSBgc3VtbWFyeWAgbWV0aG9kIG9uIHRoZSBgbG1gIG9iamVjdCwgdGhlIGJ1dHRvbSBzaG93cyBzb21lIHN0YXRpc3RpY3MuDQpgYGB7cn0NCnN1bW1hcnkoc2ltcGxlX2xtKQ0KYGBgDQoNClRoZXNlIHN0YXRpc3RpY3MgYXJlIHRoZSByZXN1bHQgb2YgcHJlZGljdGluZyB0aGUgc2FtZSBkYXRhIHRoYXQgd2FzIHVzZWQgdG8gZGVyaXZlIHRoZSBjb2VmZmljaWVudHMuIFRoaXMgaXMgcHJvYmxlbWF0aWMgYmVjYXVzZSBpdCBjYW4gbGVhZCB0byBvcHRpbWlzdGljIHJlc3VsdHMsIGVzcGVjaWFsbHkgZm9yIG1vZGVscyB0aGF0IGFyZSBleHRyZW1lbHkgZmxleGliaWxlLiANCg0KVGhlIHRlc3Qgc2V0IGlzIHVzZWQgZm9yIGFzc2Vzc2luZyBwZXJmb3JtYW5jZS4gKipTaG91bGQgd2UgcHJlZGljdCB0aGUgdGVzdCBzZXQqKiBhbmQgdXNlIHRob3NlIHJlc3VsdHMgdG8gZXN0aW1hdGUgdGhlc2Ugc3RhdGlzdGljcy4gDQoNCioqTk9QRSEqKg0KDQojIyMgQXNzZXNzaW5nIG1vZGVscw0KU2F2ZSB0aGUgdGVzdCBzZXQgdW50aWwgdGhlIHZlcnkgZW5kIHdoZW4geW91IGhhdmUgb25lIG9yIHR3byBtb2RlbHMgdGhhdCBhcmUgeW91ciBmYXZvcml0ZS4gV2UnbGwgbmVlZCB0byB1c2UgdGhlIHRyYWluaW5nIHNldCBidXQuLi4NCg0KRm9yIHNvbWUgbW9kZWxzLCBpdCBpcyBwb3NzaWJsZSB0byBnZXQgdmVyeSBzbWFsbCByZXNpZHVhbHMgYnkgcHJlZGljdGluZyB0aGUgdHJhaW5pbmcgc2V0LiBUaGF0J3MgYW4gaXNzdWUgc2luY2Ugd2Ugd2lsbCBuZWVkIHRvIG1ha2UgY29tcGFyaXNvbnMgYmV0d2VlbiBtb2RlbHMsIGNyZWF0ZSBkaWFnbm9zdGljIHBsb3RzLCBldGMuIA0KDQpJZiBvbmx5IHdlIGhhZCBhIG1ldGhvZCBmb3IgZ2V0dGluZyBob25lc3QgcGVyZm9ybWFuY2UgZXN0aW1hdGVzIGZyb20gdGhlIHRyYWluaW5nIHNldC4uDQoNCiMjIyBSZXNhbXBsaW5nIG1ldGhvZHMNCg0KVGhlcmUgYXJlIGFkZGl0aW9uYWwgZGF0YSBzcGxpdHRpbmcgc2NoZW1lcyB0aGF0IGFyZSBhcHBsaWVkIHRvICp0cmFpbmluZyBzZXQqLiBUaGV5IGF0dGVtcHQgdG8gc3RpbXVsYXRlIHNsaWdodGx5IGRpZmZlcmVudCB2ZXJzaW9ucyBvZiB0aGUgdHJhaW5nIHNldC4gVGhlc2UgdmVyc2lvbnMgb2YgdGhlIG9yaWdpbmFsIGFyZSBzcGxpdCBpbnRvIHR3byBtb2RlbCBzdWJzZXRzLiANCg0KLSBUaGUgYW5hbHlzaXMgc2V0IGlzIHVzZWQgdG8gZml0IHRoZSBtb2RlbCAoYW5hbG9nb3VzIHRvIHRoZSB0cmFpbmluZyBzZXQpDQotIFBlcmZvcm1hbmNlIGlzIGRldGVybWluZWQgdXNpbmcgdGhlIGFzc2Vzc21lbnQgc2V0Lg0KDQpUaGlzIHByb2Nlc3MgaXMgcmVwYXRlZCBtYW55IHRpbWVzLiBUaGVyZSBhcmUgZGlmZmVyZW50IGZsYXZvcnMgb3IgcmVzYW1wbGluZyBidXQgd2Ugd2lsbCBmb2N1cyBvbiB0d28gbWV0aG9kcy4NCg0KDQoNCiMjIyBWLUZvbGQgQ3Jvc3MtdmFsaWRhdGlvbg0KDQpgYGB7cn0NCmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJDOi9Vc2Vycy9rb2ppa20ubWl6dW11cmEvRGVza3RvcC9EYXRhIFNjaWVuY2UvVXNlUiAyMDE4L0FwcGxpZWQgTUwvcmVzYW1wbGluZyBtZXRob2RzLlBORyIpDQpgYGANCg0KVGhlc2UgYXJlIGFkZGl0b25hbCBkYXRhIHNwbGl0dGluZyB0aGF0IGFyZSBhcHBsaWVkIHRvIHRoZSAqdHJhaW5pbmcqIHNldC4NClRoZXkgYXR0ZW1wdCB0byBzaW1wdWF0ZSBzbGlnaHRseSBkaWZmZXJlbnQgdmVyc2lvbnMgb2YgdGhlICp0cmFpbmluZyogc2V0LiBUaGVzZSB2ZXJzaW9ucyBvZiB0aGUgb3JvZ2luYWwgYXJlIHNwbGl0IGludG8gdHdvIG1vZGVsIHN1YnNldHMuIA0KLSBUaGUgKmFuYWx5c2lzKiBzZXQgaXNlZCBvIGZpdCB0aGUgbW9kZWwgKGFuYWxvZ291cyB0byB0aGUgdHJhaW5pbmcgc2V0KQ0KLSBQZWZvcm1hbmNlIGlzIGRldGVybWluZWQgdXNpbmcgdGhlICphc3Nlc3NtZW50KiBzZXQuDQoNClRoaXMgcHJvY2VzcyBpcyByZXBlYXRlZCBtYW55IHRpbWVzLg0KDQpUaGVyZSBhcmUgZGlmZmVyZW50IGZsYXZvcnMgb3IgcmVzYW1wbGluZyBidXQgd2Ugd2lsbCBmb2N1cyBvbiB0d28gbWV0aG9kcy4NCg0KIyMjIFYtRm9sZCBDcm9zcyBWYWxpZGF0aW9uDQpIZXJlLCB3ZSByYW5kb21seSBzcGxpdCB0aGUgdHJhaW5pbmcgZGF0YSBpbnRvIFYgZGlzdGluY3QgYmxvY2tzIG9mIHJvdWdobHkgZXF1YWwgc2l6ZS4gDQotIFdlIGxlYXZlIG91dCB0aGUgZmlyc3QgYmxvY2sgb2YgYW5hbHlzaXMgZGF0YSBhbmQgZml0IGEgbW9kZWwuDQotIFRoaXMgbW9kZWwgaXMgdXNlZCB0byBwcmVkaWN0IHRoZSBoZWxkLW91dCBibG9jayBvZiBhc3Nlc3NtZW50IGRhdGEuDQotIFdlIGNvbnRpbnVlIHRoaXMgcHJvY2VzcyB1bnRpbCB3ZSd2ZSBwcmVkaWN0ZWQgYWxsIFYgYXNzZXNzbWVudCBibG9ja3MuDQoNClRoZSBmaW5hbCBwZXJmb3JtYW5jZSBpcyBiYXNlZCBvbiB0aGUgaG9sZC1vdXQgcHJlZGljdGlvbnMgYnkgKmF2ZXJhZ2luZyogdGhlIHN0YXRpc3RpY3MgZnJvbSB0aGUgViBibG9ja3MuIFYgaXMgdXN1YWxseSB0YWtlbiB0byBiZSA1IG9yIDEwIGFuZCBsZWF2ZSBvbmUgb3V0IGNyb3NzLXZhbGlkYXRpb24gaGFzIGVhY2ggc2FtcGxlIGFzIGEgYmxvY2suDQoNCiMjIyAxMC1Gb2xkIENyb3NzLVZhbGlkYXRpb24gd2l0aCBuPTUwDQpgYGB7cn0NCmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJDOi9Vc2Vycy9rb2ppa20ubWl6dW11cmEvRGVza3RvcC9EYXRhIFNjaWVuY2UvVXNlUiAyMDE4L0FwcGxpZWQgTUwvY3YtcGxvdC0xLnBuZyIpDQpgYGANCg0KIyMjIEJvb3RzdHJhcHBpbmcNCkEgKipib29zdHJhcCBzYW1wbGUqKiBpcyB0aGUgc2FtZSBzaXplIGFzIHRoZSB0cmFpbmluZyBzZXQgYnV0IGVhY2ggZGF0YSBwb2ludCBpcyBzZWxlY3RlZCB3aXRoIHJlcGxhY2VtZW50LiANCg0KVGhpcyBtZWFucyB0aGF0IHRoZSBhbmFseXNpcyBzZXQgd2lsbCBoYXZlIG1vcmUgdGhhbiBvbmUgcmVwbGljYXRlIG9mIGEgdHJhaW5pbmcgc2V0IGluc3RhbmNlLiANCg0KVGhlIGFzc2Vzc21lbnQgc2V0IGNvbnRhaW5zIGFsbCBzYW1wbGVzIHRoYXQgd2VyZSBuZXZlciBpbmNsdWRlZCBpbiB0aGUgYm9vdHN0cmFwIHNldC4gSXQgaXMgb2Z0ZW4gY2FsbGVkIHRoZSBvdXQtb2YtYmFnIHNhbXBsZSBhbmQgY2FuIHZhcnkgaW4gc2l6ZS4gDQoNCk9uIGF2ZXJhZ2UsIDYzLjEyMjA1NTklIG9mIHRoZSB0cmFpbmluZyBzZXQgaXMgY29udGFpbmVkIGF0IGxlYXN0IG9uY2UgaW4gdGhlIGJvb3RzdHJhcCBzYW1wbGUuDQoNCmBgYHtyfQ0Ka25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoIkM6L1VzZXJzL2tvamlrbS5taXp1bXVyYS9EZXNrdG9wL0RhdGEgU2NpZW5jZS9Vc2VSIDIwMTgvQXBwbGllZCBNTC9ib290LXBsb3QtMS5wbmciKQ0KYGBgDQoNCiMjIyBDb21wYXJpbmcgUmVzYW1wbGluZyBtZXRob2RzDQoNCklmIHlvdSB0aGluayBvZiByZXNhbXBsaW5nIGluIHRoZSBzYW1lIG1hbm5lciBhcyBzdGF0aXN0aWNhbCBlc3RpbWF0b3JzIChlLmcuLCBtYXhpbXVtIGxpa2VsaWhvb2QpLCB0aGlzIGJlY29tZXMgYSB0cmFkZS1vZmYgYmlhcyBhbmQgdmFyaWFuY2U6DQoNCi0gdmFyaWFuY2UgaXMgKG1vc3RseSkgZHJpdmVuIGJ5IHRoZSBudW1iZXIgb2YgcmVzYW1wbGVzIChlLmcuLCA1LWZvbGQgQ1YgbGFyZ2VyIHZhcmlhbmNlIHRoYW4gMTAtZm9sZHMpLg0KLSBCaWFzIGlzIChtb3N0bHkpIHJlbGF0ZWQgdG8gaG93IG11Y2ggZGF0YSBpcyBoZWxkIGJhY2suIFRoZSBib290c3RyYXAgaGFzIGxhcmdlIGJpYXMgY29tcGFyZWQgdG8gMTAtZm9sZCBDVi4gDQoNClRoZXJlIGFyZSBsZW5ndGggYmxvZyBwb3N0cyBhYm91dCB0aGlzIHN1YmplY3QgW2hlcmVdKGh0dHA6Ly9hcHBsaWVkcHJlZGljdGl2ZW1vZGVsaW5nLmNvbS9ibG9nLzIwMTQvMTEvMjcvdnB1aWcwMXBxYmtsbWk3MmI4bGNsM2lqNWhqMnFtKSBhbmQgW2hlcmVdKGh0dHA6Ly9hcHBsaWVkcHJlZGljdGl2ZW1vZGVsaW5nLmNvbS9ibG9nLzIwMTQvMTEvMjcvMDhrczdsZWgwem9mNDV6cGY1dnFlNTZkMXNhaGIwKS4NCg0KSSB0ZW5kIHRvIGZhdm9yIDUgcmVwZWF0cyBvZiAxMC1mb2xkIGNyb3NzLXZhbGlkYXRpb24gdW5sZXNzIHRoZSBzaXplIG9mIHRoZSBhc3Nlc3NtZW50IGRhdGEgaXMgImxhcmdlIGVub3VnaCIuDQoNCkZvciBleGFtcGxlLCAxMCUgb2YgdGhlIEFtZXMgdHJhaW5pbmcgc2V0IGlzIDIxOSBwcm9wZXJ0aWVzIGFuZCB0aGlzIGlzIHByb2JhYmx5IGdvb2QgZW5vdWdoIHRvIGVzdGltYXRlIHRoZSAkUk1TRSQgYW5kICRSXjIkLg0KDQojIyMgQ3Jvc3MtdmFsaWRhdGluZyB1c2luZyBgcnNhbXBsZWANCmBgYHtyfQ0KbGlicmFyeShBbWVzSG91c2luZykNCmxpYnJhcnkocnNhbXBsZSkNCg0Kc2V0LnNlZWQoMjQzMykNCmN2X3NwbGl0cyA8LSB2Zm9sZF9jdihhbWVzX3RyYWluLCB2PTEwLCBzdHJhdGE9IlNhbGVfUHJpY2UiKQ0KY3Zfc3BsaXRzDQpgYGANCg0KVGhlIGBzcGxpdGAgb2JqZWN0cyBjb250YWluIHRoZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgc2FtcGxlIHNpemUuDQpgYGB7cn0NCmN2X3NwbGl0cyRzcGxpdHNbWzFdXQ0KYGBgDQoNCldlIHVzZSB0aGUgYGFuYWx5c2lzYCBhbmQgYGFzc2Vzc21lbnRgIGZ1bmN0aW9ucyB0byBnZXQgdGhlIGRhdGEuDQpgYGB7cn0NCmFuYWx5c2lzKGN2X3NwbGl0cyRzcGxpdHNbWzFdXSkgJT4lIGRpbSgpDQoNCmFzc2Vzc21lbnQoY3Zfc3BsaXRzJHNwbGl0c1tbMV1dKSAlPiUgZGltKCkNCmBgYA0KDQojIyMgUmVzYW1wbGluZyB0aGUgbGluZWFyIG1vZGVsDQpXZSBXaWxsIG5lZWQgdG8gd3JpdGUgYSBmdW5jdGlvbiB0byBmaXQgdGhlIG1vZGVsIHRvIGVhY2ggZGF0YSBzZXQgYW5kIGFub3RoZXIgdG8gY29tcHV0ZSBwZXJmb3JtYW5jZS4gDQpgYGB7cn0NCmxpYnJhcnkoeWFyZHN0aWNrKQ0KDQpsbV9maXQgPC0gZnVuY3Rpb24oZGF0YV9zcGxpdCwgLi4uKXsNCiAgbG0oLi4uLCBkYXRhPWFuYWx5c2lzKGRhdGFfc3BsaXQpKX0NCg0KIyBBIGZvcm11bGEgaXMgYWxzbyBuZWVkZWQgZm9yIGVhY2ggbW9kZWw6DQpmb3JtIDwtIGFzLmZvcm11bGEoDQogIGxvZzEwKFNhbGVfUHJpY2UpfkxvbmdpdHVkZStMYXRpdHVkZSkNCmBgYA0KDQpGb3IgcGVyZm9ybWFuY2UsIHRoZSBmaXJzdCBhcmd1bWVudCBzaG91bGQgdGhlIGByc3BsaXRgIG9iamVjdGVkIGNvbnRhaW5lZCBpbiBgY3Zfc3BsaXRzJHNwbGl0czpgDQoNCmBgYHtyfQ0KDQptb2RlbF9wZXJmIDwtIGZ1bmN0aW9uKGRhdGFfc3BsaXQsIG1vZF9vYmopIHsNCiAgdmFycyA8LSByc2FtcGxlOjpmb3JtX3ByZWQobW9kX29iaiR0ZXJtcykNCiAgYXNzZXNzX2RhdCA8LSBhc3Nlc3NtZW50KGRhdGFfc3BsaXQpICU+JQ0KICAgICAgc2VsZWN0KCEhIXZhcnMsIFNhbGVfUHJpY2UpICU+JQ0KICAgICAgbXV0YXRlKA0KICAgICAgICAgIHByZWQgPSBwcmVkaWN0KA0KICAgICAgICAgICAgICBtb2Rfb2JqLCANCiAgICAgICAgICAgICAgbmV3ZGF0YSA9IGFzc2Vzc21lbnQoZGF0YV9zcGxpdCkNCiAgICAgICAgICApLA0KICAgICAgICAgIFNhbGVfUHJpY2UgPSBsb2cxMChTYWxlX1ByaWNlKQ0KICAgICAgKQ0KICBybXNlIDwtIGFzc2Vzc19kYXQgJT4lIA0KICAgICAgcm1zZSh0cnV0aCA9IFNhbGVfUHJpY2UsIGVzdGltYXRlID0gcHJlZCkNCiAgcnNxIDwtIGFzc2Vzc19kYXQgJT4lIA0KICAgICAgcnNxKHRydXRoID0gU2FsZV9QcmljZSwgZXN0aW1hdGUgPSBwcmVkKQ0KICBkYXRhLmZyYW1lKHJtc2UgPSBybXNlLCByc3EgPSByc3EpDQp9DQoNCg0KYGBgDQoNCiMjIyBSZXNhbWxpbmcgdGhlIGxpbmVhciBtb2RlbA0KDQpUaGUgYHB1cnJyYCBwYWNrYWdlIHdpbGwgYmUgdXNlZCB0byBmaXQgdGhlIG1vZGVsIHRvIGVhY2ggYW5hbHlzaXMgc2V0LiBUaGVyZSB3aWxsIGJlIHNhdmVkIGluIGEgY29sdW1uIGNhbGxlZCBgbG1fbW9kYDoNCmBgYHtyfQ0KbGlicmFyeShwdXJycikNCg0KY3Zfc3BsaXRzIDwtIGN2X3NwbGl0cyAlPiUgDQogIG11dGF0ZShsbV9tb2Q9bWFwKHNwbGl0cywgbG1fZml0LCBmb3JtdWxhPWZvcm0pKQ0KY3Zfc3BsaXRzDQpgYGANCg0KIyMjIFJlc2FtcGxpbmcgdGhlIGxpbmVhciBtb2RlbCAoY29udC4pDQpOb3csIGxldCdzIGNvbXB1dGUgdGhlIHR3byBwZXJmb3JtYW5jZSBtZWFzdXJlczoNCmBgYHtyfQ0KIyBtYXAyIGNhbiBiZSB1c2VkIHRvIG1vdmUgb3ZlciB0d28gb2JqZWN0cyBvZiBlcXVhbCBsZW5ndGgNCg0KbGlicmFyeShkcGx5cikNCmxtX3JlcyA8LSBtYXAyX2RmKGN2X3NwbGl0cyRzcGxpdHMsIGN2X3NwbGl0cyRsbV9tb2QsIG1vZGVsX3BlcmYpICU+JSANCiAgZHBseXI6OnJlbmFtZShybXNlX3NpbXBsZT1ybXNlLCByc3Ffc2ltcGxlPXJzcSkNCg0KbG1fcmVzICU+JSBoZWFkKCkNCg0KYGBgDQoNCmBgYHtyfQ0KIyBNZXJnZSBpbiByZXN1bHRzOg0KY3Zfc3BsaXRzIDwtIGN2X3NwbGl0cyAlPiUgYmluZF9jb2xzKGxtX3JlcykNCg0KIyBSZW5hbWUgdGhlIGNvbHVtbnMgYW5kIGNvbXB1dGUgdGhlIHJlc2FtcGxpbmcgZXN0aW1hdGVzOg0KY3Zfc3BsaXRzICU+JSBzZWxlY3Qocm1zZV9zaW1wbGUsIHJzcV9zaW1wbGUpICU+JSBjb2xNZWFucw0KDQpgYGANCg0KIyMjIFdoYXQgd2FzIHRoZSBydWNrdXM/DQpQcmV2aW91c2x5LCBJIG1lbnRpb25lZCB0aGF0IHRoZSBwZXJmb3JtYW5jZSBtZXRyaWNzIHRoYXQgd2VyZSBuYWl2ZWx5IGNhbGN1bGF0ZWQgZnJvbSB0aGUgdHJhaW5pbmcgc2V0IGNvdWxkIGJlIG9wdGltaXN0aWMuIEhvd2V2ZXIsIHRoaXMgYXBwcm9hY2ggZXN0aW1hdGVzIHRoZSBSTVNFIHRvIGJlIDAuMTYxNCwgYW5kIGNyb3NzLXZhbGlkYXRpb24gcHJvZHVjZWQgYW4gZXN0aW1hdGUgb2YgMC4xNjEzLiBXaGF0IHdhcyB0cmhlIGJpZyBkZWFsPw0KDQpMaW5lYXIgcmVncmVzc2lvbiBpcyBhIGhpZ2ggYmlhcyBtb2RlbC4gVGhpcyBtZWFucyB0aGF0IGl0IGlzIGZhaXJseSBpbmNhcGFibGUgYXQgYmVpZ24gYWJsZSB0byBhZHB0IHRoZSB1bmRlcmx5aW5nIG1vZGVsIGZ1bmN0aW9uICh1bmxlc3MgaXQgaXMgbGluZWFyKS4gRm9yIHRoaXMgcmVhc29uLCBsaW5lYXIgcmVncmVzc2lvbiBpcyB1bmxpa2VseSB0byBvdmVyZml0IHRvIHRoZSB0cmFpbmluZyBzZXQgYW5kIG91ciB0d28gZXN0aW1hdGVzIGFyZSBsaWtlbHkgdG8gYmUgdGhlIHNhbWUuDQoNCldlJ2xsIGNvbnNpZGVyIGFub3RoZXIgbW9kZWwgc2hvcnRseSB0aGF0IGlzIGxvdyBiaWFzIHNpbmNlIGl0IGNhbiwgdGhlb3JldGljYWxseSwgZWFzaWx5IGFkYXB0IHRvIGEgd2lkZSB2YXJpZXR5IG9mIHRydWUgbW9kZWwgZnVuY3Rpb25zLg0KDQoNCkhvd2V2ZXIsIGFzIGJlZm9yZSwgdGhlcmUgaXMgYWxzbyB2YXJpYW5jZSB0byBjb25zaWRlci4gTGluZWFyIHJlZ3Jlc3Npb24gaXMgdmVyeSBzdGFibGUgc2luY2UgaXQgbGV2ZXJhZ2VzIGFsbCBvZiB0aGUgZGF0YSBwb2ludHMgdG8gZXN0aW1hdGUgcGFyYW1ldGVycy4gT3RoZXIgbWV0aG9kcywgc3VjaCBhcyB0cmVlLWJhc2VkIG1vZGVscywgYXJlIG5vdCBhbmQgY2FuIGRyYXN0aWNhbGx5IGNoYW5nZSBpZiB0aGUgdHJhaW5pbmcgc2V0IGRhdGEgaXMgc2xpZ2h0bHkgcGVydHVyYmVkLg0KDQp0bDtkcjogdGhlIGVhcmxpZXIgY29uY2VybiBpcyByZWFsIGJ1dCBsaW5lYXIgcmVncmVzc2lvbiBpcyBsZXNzIGxpa2VseSB0byBiZSBhZmZlY3RlZC4NCg0KIyMjIERpYWdub3N0aWNzIEFnYWluDQpOb3cgbGV0J3MgbG9vayBhdCBkaWFnbm9zdGljcyB1c2luZyB0aGUgcHJlZGljdGlvbnMgZnJvbSB0aGUgYXNzZXNzbWVudCBzZXRzLg0KYGBge3J9DQpnZXRfYXNzZXNzbWVudCA8LSBmdW5jdGlvbihzcGxpdHMsIG1vZGVsKQ0KICBhdWdtZW50KG1vZGVsLCBuZXdkYXRhPWFzc2Vzc21lbnQoc3BsaXRzKSkgJT4lIA0KICBtdXRhdGUoLnJlc2lkPWxvZzEwKFNhbGVfUHJpY2UpLS5maXR0ZWQpDQoNCmhvbGRvdXRfcmVzdWx0cyA8LSBtYXAyX2RmKGN2X3NwbGl0cyRzcGxpdHMsIGN2X3NwbGl0cyRsbV9tb2QsIGdldF9hc3Nlc3NtZW50KQ0KaG9sZG91dF9yZXN1bHRzICU+JSBkaW0oKQ0KYGBgDQoNCmBgYHtyfQ0KYW1lc190cmFpbiAlPiUgZGltKCkNCmBgYA0KDQojIyMgSGFuZHMtb24gcGFydGlhbCByZXNpZHVhbCBwbG90cw0KQSBwYXJ0aWFsIHJlc2lkdWFsIHBsb3QgaXMgdXNlZCB0byBkaWFnbm9zZSB3aGF0IHZhcmlhYmxlcyBzaG91bGQgaGF2ZSBiZWVuIGluIHRoZSBtb2RlbC5XZSBjYW4gcGxvdCB0aGUgaG9sZC1vdXQgcmVzaWR1YWxzIHZlcnN1cyBkaWZmZXJlbnQgdmFyaWFibGVzIHRvIHVuZGVyc3RhbmQgaWYgdGhleSBzaG91bGQgaGF2ZSBiZWVuIGluIHRoZSBtb2RlbA0KLSBJZiB0aGUgcmVzaWR1YWxzIGhhdmUgbm8gcGF0dGVybiBpbiB0aGUgZGF0YSwgdGhleSBhcmUgbGlrZWx5IHRvIGJlIGlycmVsZXZhbnQuDQotIElmIGEgcGF0dGVybiBpcyBzZWVuLCBpdCBzdWdnZXN0cyB0aGF0IHRoZSB2YXJpYWJsZSBzaG91bGQgaGF2ZSBiZWVuIGluIHRoZSBtb2RlbC4NCg0KVGFrZSAxMCBtaW4gYW5kIHVzZSBgZ2dwbG90YCB0byBpbnZlc3RpZ2F0ZSBvdGhlciBwcmVkaWN0b3JzIHVzaW5nIHRoZSBgaG9sZG91dF9yZXN1bHRzYCBkYXRhIGZyYW1lLiBgZ2VvbV9zbW9vdGhgIG1pZ2h0IGNvbWUgaW4gaGFuZHkuDQoNCiMjIFR1bmluZyBwYXJhbWV0ZXJzIGFuZCBvdmVyZml0dGluZw0KIyMjIEstTmVhcmVzdCBOZWlnaGJvcnMgTW9kZWwNCg0KTm93IGxldCdzIGNvbnNpZGVyIGEgbW9yZSBmbGV4aWJsZSBtb2RlbCB0aGF0IGlzIGxvdyBiYXM6IEstbmVhcmVzdCBuZWlnaGJvcnMuVGhlIG1vZGVsIHN0b3JlcyB0aGUgdHJhaW5pbmcgc2V0KGluY2x1ZGluZyB0aGUgb3V0Y29tZSkuIFdoZW4gYSBuZXcgc2FtcGxlIGlzIHByZWRpY3RlZCwgJEskIHRyYWluaW5nIHNldCBwb2ludHMgYXJlIGZvdW5kIHRoYXQgYXJlIG1vc3Qgc2ltaWxhciB0byB0aGUgbmV3IHNhbXBsZSBiZWluZyBwcmVkaWN0ZWQuDQoNClRoZSBwcmVkaWN0ZWQgdmFsdWUgZm9yIHRoZSBuZXcgc2FtcGxlIGlzIHNvbWUgc3VtbWFyeSBzdGF0aXN0aWMgb2YgdGhlIG5laWdoYm9ycywgdXN1YWxseToNCi0gdGhlIG1lYW4gZm9yIHJlZ3Jlc3Npb24sIG9yDQotIHRoZSBtb2RlIGZvciBjbGFzc2lmaWNhdGlvbg0KDQpXaGVuICRLJCBpcyBzbWFsbCwgdGhlIG1vZGVsIG1pZ2h0IGJlIHRvbyByZXNwb25zaXZlIHRvIHVuZGVybHlpbmcgZGF0YS4gV2hlbiAkSyQgaXMgbGFyZ2UsIGl0IGJlZ2lucyB0byAib3ZlcnNtb290aCIgdGhlIG5laWdoYm9ycyBhbmQgcGVyZm9ybWFuY2Ugc3VmZmVycy4NCg0KT3JkaW5hcnksIHNpbmNlIHdlIGFyZSBjb21wdXRpbmcgYSAqKmRpc3RhbmNlKiosIHdlIHdvdWxkIHdhbnQgdG8gY2VudGVyIGFuZCBzY2FsZSB0aGUgcHJlZGljdG9ycy4gT3VyIHR3byBwcmVkaWN0b3JzIGFyZSBhbHJlYWR5IG9uIHRoZSBzYW1lIHNjYWxlIHNvIHdlIGNhbiBza2lwIHRoaXMgc3RlcC4NCg0KQ29uc2lkZXIgdGhlIDItbmVhcmVzdCBuZWlnaGJvciBtb2RlbC4gV291bGQgdGhlcmUgYmUgYSBkaWZmZXJlbmNlIGluIHRoZSBlc3RpbWF0ZWQgbW9kZWwgcGVyZm9ybWFuY2UgYmV0d2VlbiByZS1wcmVkaWN0aW9uIGFuZCBjcm9zcy12YWxpZGF0aW9uPw0KDQpgY2FyZXRgIGhhcyBhIGBrbm5yZWdgIGZ1bmN0aW9uIHRoYXQgY2FuIGJlIHVzZWQgKHRoZSBga2tubmAgcGFja2FnZSBpcyBhbm90aGVyIG9wdGlvbikuIElUIGhhcyBhIGZvcm11bGEgbWV0aG9kIGFuZCB3ZSdsbCB1c2UgdGhpcyB0byBpbGx1c3RyYXRlIHRoZSBtb2RlbDoNCmBgYHtyfQ0KbGlicmFyeShjYXJldCkNCg0Ka25uX3RyYWluX21vZCA8LSBrbm5yZWcobG9nMTAoU2FsZV9QcmljZSl+TG9uZ2l0dWRlK0xhdGl0dWRlLA0KICAgICAgICAgICAgICAgICAgICAgICAgZGF0YT1hbWVzX3RyYWluLA0KICAgICAgICAgICAgICAgICAgICAgICAgaz0yKQ0KDQpyZXByZWRpY3QgPC0gZGF0YS5mcmFtZShwcmljZT1sb2cxMChhbWVzX3RyYWluJFNhbGVfUHJpY2UpKSAlPiUgDQogIG11dGF0ZShwcmVkPXByZWRpY3Qoa25uX3RyYWluX21vZCwgbmV3ZGF0YT1hbWVzX3RyYWluICU+JSBzZWxlY3QoTG9uZ2l0dWRlLExhdGl0dWRlKQ0KICAgICAgICAgICAgICAgICAgICAgICkNCiAgICAgICAgICkNCg0KcmVwcmVkaWN0ICU+JSByc3EodHJ1dGggPSAicHJpY2UiLCBlc3RpbWF0ZSA9ICJwcmVkIikgIyA8LSB0aGUgcnVja3VzIGlzIGhlcmUNCiMgMC44OTI4NzINCmBgYA0KDQpUaGF0cyBwcmV0dHkgZ29vZCwgYnV0IGFyZSB3ZSB0cmlja2luZyBvdXJzZWx2ZXM/IE9uZSBvZiB0aG9zZSB0d28gbmVpZ2hib3JzIGlzIGFsd2F5cyBpdHNlbGYuIFRvIHJlc2FtcGxlLCBsZXQncyBjcmVhdGUgYW5vdGhlciBmdW5jdGlvbiB0byBmaXQgdGhpcyBtb2RlbCBhbmQgZm9sbG93IHRoZSBzYW1lIHJlc2FtcGxpbmcgcHJvY2VzcyBhcyBiZWZvcmU6DQpgYGB7cn0NCmtubl9maXQgPC0gZnVuY3Rpb24oZGF0YV9zcGxpdCwuLi4pDQogIGtubnJlZyguLi4sIGRhdGE9YW5hbHlzaXMoZGF0YV9zcGxpdCkpDQoNCmN2X3NwbGl0cyA8LSBjdl9zcGxpdHMgJT4lIA0KICBtdXRhdGUoa25uX21vZD1tYXAoc3BsaXRzLCBrbm5fZml0LCBmb3JtdWxhPWZvcm0sIGs9MikpDQoNCmtubl9yZXMgPC0gbWFwMl9kZihjdl9zcGxpdHMkc3BsaXRzLCBjdl9zcGxpdHMka25uX21vZCwgbW9kZWxfcGVyZikgJT4lIA0KICByZW5hbWUocm1zZV9rbm49cm1zZSwgcnNxX2tubj1yc3EpDQoNCiMgbWVyZ2UgaW4gcmVzdWx0cw0KY3Zfc3BsaXRzIDwtIGN2X3NwbGl0cyAlPiUgYmluZF9jb2xzKGtubl9yZXMpDQoNCmNvbE1lYW5zKGtubl9yZXMpDQpgYGANCg0KIyMjIE1ha2luZyBmb3JtYWwgY29tcGFyaXNvbnMNClRoZSBtb2RlbCBhcHBlYXJzIHRvIGJlIGEgZHJhc3RpYyBpbXByb3ZlbWVudCBvdmVyIHNpbXBsZSBsaW5lYXIgcmVncmVzc2lvbiwgYnV0IHdlIGFyZSBkZWZpbml0ZWx5IGdldHRpbmcgaGlnaGx5IG9wdGltaXN0aWMgcmVzdWx0cyBieSByZS1wcmVkaWN0aW5nIHRoZSB0cmFpbmluZyBzZXQuDQoNCldlIGNhbiB0cnkgdG8gbWFrZSBhIG1vcmUgZm9ybWFsIGFzc2VzbWVudCBvZiB0aGUgdHdvIGN1cnJlbnQgbW9kZWxzLiBCb3RoIG1vZGVscyB1c2VkIHRoZSBzYW1lIHJlc2FtcGxlcywgc28gd2UgaGF2ZSAxMCBlc3RpbWF0ZXMgb2YgcGVyZm9ybWFuY2UgdGhhdCBhcmUgbWF0Y2hlZC4gRG9lcyB0aGUgbWF0Y2hpbmcgbWVhbiBhbnl0aGluZz8gDQoNCk1vc3QgbGlrZWx5ICoqWUVTKiouIEl0IGlzIHZlcnkgY29tbW9uIHRvIHNlZSB0aGF0IHRoZXJlIGlzIGEgcmVzYW1wbGUgZWZmZWN0LiBTaW1pbGFyIHRvIHJlcGVhdGVkIG1lYXN1cmVzIGRlc2lnbnMsIHdlIGNhbiBleHBlY3QgYSByZWxhdGlvbnNoaXAgYmV0d2VlbiBtb2RlbHMgYW5kIHJlc2FtcGxlcy4gRm9yIGV4YW1wbGUsIHNvbWUgcmVzYW1wbGVzIHdpbGwgaGF2ZSB0aGUgd29yc3QgcGVyZm9ybWFuY2Ugb3ZlciBkaWZmZXJlbnQgbW9kZWxzIGFuZCBzbyBvbi4gDQoNCkluIG90aGVyIHdvcmRzLCB0aGVyZSBpcyB1c3VhbGx5IGEgd2l0aGluLXJlc2FtcGxlIGNvcnJlbGF0aW9uLiBGb3IgdGhlIHR3byBtb2RlbHMsIHRoZSBlc3RpbWF0ZWQgY29ycmVsYXRpb24gaW4gUk1TRSB2YWx1ZXMgaXMgMC44NS4NCg0KIyMjIFRoZSByZXNhbXBsZSBlZmZlY3QNCmBgYHtyfQ0KcnNfY29tcCA8LSBkYXRhLmZyYW1lKA0KCXJtc2UgPSBjKGN2X3NwbGl0cyRybXNlX3NpbXBsZSwgY3Zfc3BsaXRzJHJtc2Vfa25uKSwNCglNb2RlbCA9IHJlcChjKCJMaW5lYXJcblJlZ3Jlc3Npb24iLCAiMi1OTiIpLCBlYWNoID0gbnJvdyhjdl9zcGxpdHMpKSwNCglSZXNhbXBsZSA9IGN2X3NwbGl0cyRpZA0KKQ0KDQpyc19jb21wDQoNCmdncGxvdChyc19jb21wLCBhZXMoeCA9IE1vZGVsLCB5ID0gcm1zZSwgZ3JvdXAgPSBSZXNhbXBsZSwgY29sID0gUmVzYW1wbGUpKSArIA0KICBnZW9tX3BvaW50KCkgKyANCiAgZ2VvbV9saW5lKCkgKyANCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQ0KDQpgYGANCg0KIyMjIE1vZGVsIGNvbXBhcmlzb24gYWNjb3VudGluZyBmb3IgcmVzYW1wbGluZw0KV2l0aCBvbmx5IHR3byBtb2RlbHMsIGEgcGFpcmVkIHQtdGVzdCBjYW4gYmUgdXNlZCB0byBlc3RpbWF0ZSB0aGUgZGlmZmVyZW5jZSBpbiBSTVNlIGJldHdlZW4gdGhlIG1vZGVsczoNCmBgYHtyfQ0KdC50ZXN0KGN2X3NwbGl0cyRybXNlX3NpbXBsZSwgY3Zfc3BsaXRzJHJtc2Vfa25uLCBwYWlyZWQ9VFJVRSkNCmBgYA0KDQpIb3Rob3JuIGV0IGFsICgyMDEyKSBpcyB0aGUgW29yaWdpbmFsIHBhcGVyXShodHRwczovL3NjaG9sYXIuZ29vZ2xlLmNvbS9zY2hvbGFyP2hsPWVuJnE9YW5hbHlzaXMrb2YrYmVuY2htYXJrK2V4cGVyaW1lbnRzJmJ0bkc9JmFzX3NkdD0xJTJDNyZhc19zZHRwPSkgb24gY29tcGFyaW5nIG1vZGVscyB1c2luZyByZXNhbXBsaW5nLg0KDQpXZSdsbCBkbyBtb3JlIGV4dGVuc2l2ZSBhbmFseXNlcyB3aXRoIHRpZHlwb3N0ZXJpb3Igc29vbi4NCg0KIyMjIE92ZXJmaXR0aW5nDQoNCk92ZXJmaXR0aW5nIG9jY3VycyB3aGVuIGEgbW9kZWwgaW5hcHByb3ByaWF0ZWx5IHBpY2sgdXAgb24gdHJlbmRzIGluIHRoZSB0cmFpbmluZyBzZXQgdGhhdCBkbyBub3QgZ2VuZXJhbGl6ZSB0byBuZXcgc2FtcGxlcy4gV2hlbiB0aGlzIG9jY3VycywgYXNzZXNtZW50IG9mIHRoZSBtb2RlbCBiYXNlZCBvbiB0aGUgdHJhaW5pbmcgc2V0IGNhbiBzaG93IGdvb2QgcGVyZm9ybWFuY2UgdGhhdCBkb2VzIG5vdCByZXByb2R1Y2UgaW4gZnV0dXJlIHNhbXBsZXMuDQoNClNvbWUgbW9kZWxzIGhhdmUgc3BlY2lmaWMgImtub2JzIiB0byBjb250cm9sIG92ZXItZml0dGluZw0KLSBuZWlnaGJvcmhvb2Qgc2l6ZSBpbiBuZWFyZXN0IG5laWdoYm9yIG1vZGVscyBpcyBhbiBleGFtcGxlDQotIHRoZSBudW1iZXIgb2Ygc3BsaXRzIGluIGEgdHJlZSBtb2RlbA0KDQpvZnRlbiBwb29yIGNob2ljZXMgZm9yIHRoZXNlIHBhcmFtZXRlcnMgY2FuIHJlc3VsdCBpbiBvdmVyZml0dGluZw0KDQpGb3IgZXhhbXBsZSwgdGhlIG5leHQgc2xpZGUgc2hvd3MgYSBkYXRhIHNldCB3aXRoIHR3byBwcmVkaWN0b3JzLiBXZSB3YW50IHRvIGJlIGFibGUgdG8gcHJvZHVjZSBhIGxpbmUgKGkuZS4sIGRlY2lzaW9uIGJvdW5kYXJ5KSB0aGF0IGRpZmZlcmVudGlhdGVzIHR3byBjbGFzc2VzIG9mIGRhdGEuDQoNCiMjIyBUd28gY2xhc3MgZXhhbXBsZSwNCk9uIHRoZSBuZXh0IHNsaWRlLCB0d28gY2xhc3NpZmljYXRpb24gYm91bmRhcmllcyBhcmUgc2hvd24gZm9yIGEgZGlmZmVyZW50IG1vZGVsIHR5cGUgbm90IHlldCBkaXNjdXNzZWQuIFRoZSBkaWZmZXJlY2UgaW4gdGhlIHR3byBwYW5lcyBpcyBzb2xlbHkgZHVlIHRvIGRpZmZlcmVudCBjaG9pY2VzIGluIHR1bmluZyBwYXJhbWV0ZXJzLiBPbmUgb3ZlcmZpdHMgdGhlIHRyYWluaW5nIGRhdGEuIA0KYGBge3J9DQprbml0cjo6aW5jbHVkZV9ncmFwaGljcygiQzovVXNlcnMva29qaWttLm1penVtdXJhL0Rlc2t0b3AvRGF0YSBTY2llbmNlL1VzZVIgMjAxOC9BcHBsaWVkIE1ML3R3by1jbGFzcy1vdmVyZml0LTEucG5nIikNCmBgYA0KDQpXZSB1c3VhbGx5IGRvbid0IGhhdmUgdHdvLWRpbWVuc2lvbmFsIGRhdGEgc28gYSBxdWFudGl0YXRpdmUgbWV0aG9kIGZvciB1bmRlciBtZWFzdXJlaW5nIG92ZXJmaXR0aW5nIGlzIG5lZWRlZC4gKipSZXNhbXBsaW5nKiogZml0cyB0aGF0IGRlc2NyaXB0aW9uLiBBIHNpbXBsZSBtZXRob2QgZm9yIHR1bmluZyBhIG1vZGVsIGlzIHVzZWQgdG8gZ3JpZCBzZWFyY2g6DQoNCuKUnOKUgOKUgCBDcmVhdGUgYSBzZXQgb2YgY2FuZGlkYXRlIHR1bmluZyBwYXJhbWV0ZXIgdmFsdWVzDQrilJTilIDilIAgRm9yIGVhY2ggcmVzYW1wbGUNCuKUgiAgIOKUnOKUgOKUgCBTcGxpdCB0aGUgZGF0YSBpbnRvIGFuYWx5c2lzIGFuZCBhc3Nlc3NtZW50IHNldHMNCuKUgiAgIOKUnOKUgOKUgCBbcHJlcHJvY2VzcyBkYXRhXQ0K4pSCICAg4pSc4pSA4pSAIEZvciBlYWNoIHR1bmluZyBwYXJhbWV0ZXIgdmFsdWUNCuKUgiAgIOKUgiAgIOKUnOKUgOKUgCBGaXQgdGhlIG1vZGVsIHVzaW5nIHRoZSBhbmFseXNpcyBzZXQNCuKUgiAgIOKUgiAgIOKUlOKUgOKUgCBDb21wdXRlIHRoZSBwZXJmb3JtYW5jZSBvbiB0aGUgYXNzZXNzbWVudCBzZXQgYW5kIHNhdmUgDQrilJzilIDilIAgRm9yIGVhY2ggdHVuaW5nIHBhcmFtZXRlciB2YWx1ZSwgYXZlcmFnZSB0aGUgcGVyZm9ybWFuY2Ugb3ZlciByZXNhbXBsZXMNCuKUnOKUgOKUgCBEZXRlcm1pbmUgdGhlIGJlc3QgdHVuaW5nIHBhcmFtZXRlciB2YWx1ZQ0K4pSU4pSA4pSAIENyZWF0ZSB0aGUgZmluYWwgbW9kZWwgd2l0aCB0aGUgb3B0aW1hbCBwYXJhbWV0ZXIocykgb24gdGhlIHRyYWluaW5nIHNldA0KDQoqKlJhbmRvbSBzZWFyY2gqKiBpcyBhIHNpbWlsYXIgdGVjaG5pcXVlIHdoZXJlIHRoZSBjYW5kaWRhdGUgc2V0IG9mIHBhcmFtZXRlciB2YWx1ZXMgYXJlIHNpbXVsYXRlZCBhdCByYW5kb20gYWNyb3NzIGEgd2lkZSByYW5nZS4gQWxzbywgYW4gZXhhbXBsZSBvZiBuZXN0ZWQgcmVzYW1wbGluZyBjYW4gYmUgZm91bmQgW2hlcmVdKGh0dHA6Ly9hcHBsaWVkcHJlZGljdGl2ZW1vZGVsaW5nLmNvbS9ibG9nLzIwMTcvOS8yL25qZGM4M2QwMXB6eXN2dmxnaWswMnQ1cW5hbGpuZCkuDQoNCiMjIyBHcmlkIHNlYXJjaCBjb21wdXRhdGlvbnMNCg0KVGhlIGJhZCBuZXdzIGlzIHRoYXQgYWxsIG9mIHRoZSBtb2RlbHMgKGV4Y2VwdCB0aGUgZmluYWwgbW9kZWwpIGFyZSBkaXNjYXJlZC4gSG93ZXZlciwgYXMgdGhlIGdvb2QgbmV3cywgYWxsIG9mIHRoZSBtb2RlbHMgKGV4Y2VwdCB0aGUgZmluYWwgbW9kZWwpIGNhbiBiZSBydW4gaW4gcGFyYWxsZWwuIExldCdzIGxvb2sgYXQgdGhlIEFtZXMgSy1OTiBtb2RlbCBhbmQgZXZhbHVhdGUgJEs9MSwyLFxkb3QsMjAkIHVzaW5nIHRoZSBzYW1lIDEwLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiBhcyBiZWZvcmUuIA0KDQpXZSdsbCBzdGFydCBjb2RpbmcgdGhpcyBhbGdvcml0aG0gZnJvbSB0aGUgaW5zaWRlIG91dC4NCg0KVGhlc2Ugc3RlcHMgYXJlOg0KIOKUnOKUgOKUgCBGaXQgdGhlIG1vZGVsIHVzaW5nIHRoZSBhbmFseXNpcyBzZXQgDQogICDilJTilIDilIAgQ29tcHV0ZSB0aGUgcGVyZm9ybWFuY2Ugb24gdGhlIGFzc2Vzc21lbnQgc2V0IGFuZCBzYXZlICANCg0KYHNwbGl0YCB3aWxsIGJlIHRoZSBvbmUgb2YgZWxlbWVudHMgb2YgYGN2X3NwbGl0cyRzcGxpdHNgLg0KYGBge3J9DQprbm5fcm1zZSA8LSBmdW5jdGlvbihrLCBzcGxpdCkgew0KICAgIG1vZCA8LSBrbm5yZWcobG9nMTAoU2FsZV9QcmljZSkgfiBMb25naXR1ZGUgKyBMYXRpdHVkZSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEgPSBhbmFseXNpcyhzcGxpdCksICANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgayA9IGspDQogICAgIyBFeHRyYWN0IHRoZSBuYW1lcyBvZiB0aGUgcHJlZGljdG9ycw0KICAgIHByZWRzIDwtIGZvcm1fcHJlZChtb2QkdGVybXMpDQogICAgZGF0YS5mcmFtZShTYWxlX1ByaWNlID0gbG9nMTAoYXNzZXNzbWVudChzcGxpdCkkU2FsZV9QcmljZSkpICU+JQ0KICAgICAgICBtdXRhdGUocHJlZCA9IHByZWRpY3QobW9kLCBhc3Nlc3NtZW50KHNwbGl0KSAlPiUgc2VsZWN0KCEhIXByZWRzKSkpICU+JQ0KICAgICAgICBybXNlKFNhbGVfUHJpY2UsIHByZWQpDQp9DQpgYGANCg0KIyMjIEZpdCB0aGUgbW9kZWwgYWNyb3NzIHZhbHVlcyBvZiBLDQoNCuKUgiAgIOKUnOKUgOKUgCBGb3IgZWFjaCB0dW5pbmcgcGFyYW1ldGVyIHZhbHVlIA0K4pSCICAg4pSCICAg4pSU4pSA4pSAIFJ1biBga25uX3Jtc2VgIA0KDQpgYGB7cn0NCmtubl9ncmlkIDwtIGZ1bmN0aW9uKHNwbGl0KSB7DQogICAgIyBDcmVhdGUgZ3JpZA0KICB0aWJibGUoayA9IDE6MjApICU+JQ0KICAgICMgRXhlY3V0ZSBncmlkIGZvciB0aGlzIHJlc2FtcGxlDQogICAgbXV0YXRlKA0KICAgICAgcm1zZSA9IG1hcF9kYmwoaywga25uX3Jtc2UsIHNwbGl0ID0gc3BsaXQpLA0KICAgICAgIyBBdHRhY2ggdGhlIHJlc2FtcGxlIGluZGljYXRvcnMgdXNpbmcgYGxhYmxlc2ANCiAgICAgIGlkID0gbGFiZWxzKHNwbGl0KVtbMV1dDQogICAgKQ0KfQ0KYGBgDQoNClRoZSByZXR1cm4gdmFsdWVzIGhlcmUgaXMgYSB0aWJibGUgd2l0aCBjb2x1bW5zIGZvciAqayosIHRoZSAqUk1TRSosIGFuZCB0aGUgZm9sZCBJRCAoZS5nLiwgYEZvbGQwMWApLg0KDQojIyMgVG9wLWxldmVsIGl0ZXJhdGlvbiBvdmVyIHJlc2FtcGxlcw0KDQrilJTilIDilIAgRm9yIGVhY2ggcmVzYW1wbGUgDQrilIIgICDilJTilIDilIAgUnVuIGBrbm5fZ3JpZGAgDQoNCkhlcmUsIGByZXNhbXBgIGlzIHRoZSByZXNhbXBsZSBvYmplY3QgYGN2X3NwbGl0c2ANCmBgYHtyfQ0KaXRlcl9vdmVyX3Jlc2FtcGxlcyA8LSANCiAgICBmdW5jdGlvbihyZXNhbXApIA0KICAgICAgICBtYXBfZGYocmVzYW1wJHNwbGl0cywga25uX2dyaWQpDQpgYGANCg0KIyMjIFJ1bm5pbmcgdGhlIGNvZGUNCmBgYHtyfQ0KbGlicmFyeShyc2FtcGxlKQ0Ka25uX3R1bmVfcmVzIDwtIGl0ZXJfb3Zlcl9yZXNhbXBsZXMoY3Zfc3BsaXRzKQ0Ka25uX3R1bmVfcmVzICU+JSBoZWFkKDE1KQ0KYGBgDQoNCiMjIyBUaGUgcGVyZm9ybWFuY2UgcHJvZmlsZQ0KVG8gc3VtbWFyaXplIHRoZSByZXN1bHRzIGZvciBlYWNoIHZhbHVlIG9mICRLJDoNCmBgYHtyfQ0KbGlicmFyeSh0aWR5dmVyc2UpDQoNCnJtc2VfYnlfayA8LSBrbm5fdHVuZV9yZXMgJT4lIA0KICBncm91cF9ieShrKSAlPiUgDQogIHN1bW1hcml6ZShybXNlPW1lYW4ocm1zZSkpDQoNCmdncGxvdChybXNlX2J5X2ssIGFlcyh4PWssIHk9cm1zZSkpKw0KICBnZW9tX3BvaW50KCkrZ2VvbV9saW5lKCkNCmBgYA0KDQpBbHRob3VnaCBpdCBpcyBudW1lcmljYWxseSBvcHRpbWFsLCB3ZSBhcmUgbm90IHJlcXVpcmVkIHRvIHVzZSBhIHZhbHVlIG9mIDQgbmVpZ2hib3JzIGZvciB0aGUgZmluYWwgbW9kZWwuDQoNCiMjIyBSZXNhbXBsaW5nIHZhcmlhdGlvbg0KDQpIb3cgc3RhYmxlIGlzIHRoaXM/IFdlIGNhbiBhbHNvIHBsb3QgdGhlIGluZGl2aWR1YWwgY3VydmVzIGFuZCB0aGVpciBtaW5pbXVtcy4NCmBgYHtyfQ0KDQpgYGANCg0KDQoNCg0K